{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Zuma Game"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #breadth-first-search #memoization #string #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #广度优先搜索 #记忆化搜索 #字符串 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findMinStep"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #祖玛游戏"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你正在参与祖玛游戏的一个变种。</p>\n",
    "\n",
    "<p>在这个祖玛游戏变体中，桌面上有 <strong>一排</strong> 彩球，每个球的颜色可能是：红色 <code>'R'</code>、黄色 <code>'Y'</code>、蓝色 <code>'B'</code>、绿色 <code>'G'</code> 或白色 <code>'W'</code> 。你的手中也有一些彩球。</p>\n",
    "\n",
    "<p>你的目标是 <strong>清空</strong> 桌面上所有的球。每一回合：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>从你手上的彩球中选出 <strong>任意一颗</strong> ，然后将其插入桌面上那一排球中：两球之间或这一排球的任一端。</li>\n",
    "\t<li>接着，如果有出现 <strong>三个或者三个以上</strong> 且 <strong>颜色相同</strong> 的球相连的话，就把它们移除掉。\n",
    "\t<ul>\n",
    "\t\t<li>如果这种移除操作同样导致出现三个或者三个以上且颜色相同的球相连，则可以继续移除这些球，直到不再满足移除条件。</li>\n",
    "\t</ul>\n",
    "\t</li>\n",
    "\t<li>如果桌面上所有球都被移除，则认为你赢得本场游戏。</li>\n",
    "\t<li>重复这个过程，直到你赢了游戏或者手中没有更多的球。</li>\n",
    "</ul>\n",
    "\n",
    "<p>给你一个字符串 <code>board</code> ，表示桌面上最开始的那排球。另给你一个字符串 <code>hand</code> ，表示手里的彩球。请你按上述操作步骤移除掉桌上所有球，计算并返回所需的 <strong>最少</strong> 球数。如果不能移除桌上所有的球，返回 <code>-1</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>board = \"WRRBBW\", hand = \"RB\"\n",
    "<strong>输出：</strong>-1\n",
    "<strong>解释：</strong>无法移除桌面上的所有球。可以得到的最好局面是：\n",
    "- 插入一个 'R' ，使桌面变为 WRR<em><strong>R</strong></em>BBW 。W<em><strong>RRR</strong></em>BBW -&gt; WBBW\n",
    "- 插入一个 'B' ，使桌面变为 WBB<em><strong>B</strong></em>W 。W<em><strong>BBB</strong></em>W -&gt; WW\n",
    "桌面上还剩着球，没有其他球可以插入。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>board = \"WWRRBBWW\", hand = \"WRBRW\"\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>要想清空桌面上的球，可以按下述步骤：\n",
    "- 插入一个 'R' ，使桌面变为 WWRR<strong><em>R</em></strong>BBWW 。WW<em><strong>RRR</strong></em>BBWW -&gt; WWBBWW\n",
    "- 插入一个 'B' ，使桌面变为 WWBB<em><strong>B</strong></em>WW 。WW<em><strong>BBB</strong></em>WW -&gt; <em><strong>WWWW</strong></em> -&gt; empty\n",
    "只需从手中出 2 个球就可以清空桌面。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>board = \"G\", hand = \"GGGGG\"\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>要想清空桌面上的球，可以按下述步骤：\n",
    "- 插入一个 'G' ，使桌面变为 G<em><strong>G</strong></em> 。\n",
    "- 插入一个 'G' ，使桌面变为 GG<em><strong>G</strong></em> 。<em><strong>GGG</strong></em> -&gt; empty\n",
    "只需从手中出 2 个球就可以清空桌面。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>board = \"RBYYBBRRB\", hand = \"YRBGB\"\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>要想清空桌面上的球，可以按下述步骤：\n",
    "- 插入一个 'Y' ，使桌面变为 RBYY<em><strong>Y</strong></em>BBRRB 。RB<em><strong>YYY</strong></em>BBRRB -&gt; R<em><strong>BBB</strong></em>RRB -&gt; <em><strong>RRR</strong></em>B -&gt; B\n",
    "- 插入一个 'B' ，使桌面变为 B<em><strong>B</strong></em> 。\n",
    "- 插入一个 'B' ，使桌面变为 BB<em><strong>B</strong></em> 。<em><strong>BBB</strong></em> -&gt; empty\n",
    "只需从手中出 3 个球就可以清空桌面。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= board.length &lt;= 16</code></li>\n",
    "\t<li><code>1 &lt;= hand.length &lt;= 5</code></li>\n",
    "\t<li><code>board</code> 和 <code>hand</code> 由字符 <code>'R'</code>、<code>'Y'</code>、<code>'B'</code>、<code>'G'</code> 和 <code>'W'</code> 组成</li>\n",
    "\t<li>桌面上一开始的球中，不会有三个及三个以上颜色相同且连着的球</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [zuma-game](https://leetcode.cn/problems/zuma-game/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [zuma-game](https://leetcode.cn/problems/zuma-game/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"WRRBBW\"\\n\"RB\"', '\"WWRRBBWW\"\\n\"WRBRW\"', '\"G\"\\n\"GGGGG\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "found={\"RRGGBBYYWWRRGGBB{'R': 1, 'Y': 1, 'B': 1, 'G': 1, 'W': 1}\":-1,\n",
    "\"RBYYBBRRB{'R': 1, 'Y': 1, 'B': 2, 'G': 1, 'W': 0}\":3,\n",
    "\"WWRBBWWGGBBRRGWB{'R': 0, 'Y': 0, 'B': 2, 'G': 2, 'W': 1}\":-1,\n",
    "\"YYRGWRBYGGBGBGWY{'R': 1, 'Y': 1, 'B': 1, 'G': 1, 'W': 1}\":-1,\n",
    "\"WRBWYGRGYGWWBWRW{'R': 1, 'Y': 1, 'B': 1, 'G': 1, 'W': 1}\":-1,\n",
    "}\n",
    "reDic={\"R\":\"GG|BB|WW|YY\",\"G\":\"RR|BB|WW|YY\",\"B\":\"RR|GG|WW|YY\",\"W\":\"RR|GG|BB|YY\",\"Y\":\"RR|GG|BB|WW\"}\n",
    "class Solution:\n",
    "    def findMinStep(self, board: str, hand: str) -> int:\n",
    "        d = {\"R\":0, \"Y\": 0, \"B\": 0, \"G\": 0, \"W\": 0}\n",
    "        for c in hand:\n",
    "            d[c] += 1\n",
    "        return self._findMinStep(board, d)\n",
    "    def _findMinStep(self, board, hand):\n",
    "        board = self.eliminate(board)\n",
    "        if not board:\n",
    "            return 0\n",
    "        minstep = 100\n",
    "        if board+str(hand) in found:\n",
    "            return found[board+str(hand)]\n",
    "        d = hand\n",
    "        for k, v in hand.items():\n",
    "            if v == 0:\n",
    "                continue\n",
    "            d[k] = v-1\n",
    "            for m in re.finditer(reDic[k],board):\n",
    "                    ms = m.start()\n",
    "                    newBoard = board[:ms+1]+k+board[ms+1:]\n",
    "                    res = self._findMinStep(newBoard, d)\n",
    "                    if res != -1:\n",
    "                        minstep = min(res + 1, minstep)\n",
    "            for m in re.finditer(\"(%s[^%s])|(%s$)\"%(k,k,k), board):\n",
    "                    ms = m.start()\n",
    "                    newBoard = board[:ms]+k+board[ms:]\n",
    "                    res = self._findMinStep(newBoard, d)\n",
    "                    if res != -1:\n",
    "                        minstep = min(res + 1, minstep)\n",
    "            d[k] = v\n",
    "        if minstep == 100:\n",
    "            return -1\n",
    "        return minstep\n",
    "    def eliminate(self, s: str):\n",
    "        r = re.compile(\"RR+R|YY+Y|BB+B|GG+G|WW+W\")\n",
    "        cnt = 1\n",
    "        while cnt != 0:\n",
    "            s, cnt = r.subn(\"\", s)\n",
    "        return s\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "import random\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.不同玩法的最小总步数 = None\n",
    "        self.手上球数 = None\n",
    "        self.当前步数 = 0\n",
    "    def findMinStep(self, board: str, hand: str) -> int:\n",
    "        # 初始化: 手上球数字典 \n",
    "        if self.手上球数 is None:\n",
    "           self.手上球数 = {}\n",
    "           for i in range(len(hand)):\n",
    "             if hand[i] not in self.手上球数:\n",
    "                self.手上球数[hand[i]] = 1\n",
    "             else:\n",
    "                self.手上球数[hand[i]] += 1 \n",
    "        # 按不同玩法疯狂插球中...\n",
    "        self.插球(board)\n",
    "        # 返回不同玩法的最小总步数\n",
    "        return self.不同玩法的最小总步数 if self.不同玩法的最小总步数 else -1\n",
    "    def 插球(self, board: str) -> None: \n",
    "        # “只能插在同色块并尝试消球”是不充分的思路，存在“插在其它颜色中间并最终成功减少总插球数”的情形\n",
    "        if len(board) == 0: # 成功完全消除 \n",
    "           self.不同玩法的最小总步数 = self.当前步数 if not self.不同玩法的最小总步数 else min(self.不同玩法的最小总步数, self.当前步数)\n",
    "           return \n",
    "        if (self.不同玩法的最小总步数 and self.不同玩法的最小总步数<=self.当前步数+1): # 超限或手上没球时停止\n",
    "           return   \n",
    "        for k in set(list(board)):\n",
    "            count_k = board.count(k)\n",
    "            k_in_手上球数 = k in self.手上球数\n",
    "            if (not k_in_手上球数 and count_k<3) or (k_in_手上球数 and count_k+self.手上球数[k]<3): # 手上没球时停止\n",
    "               return\n",
    "        for k, v in self.手上球数.items(): # 寻找球色\n",
    "          if v >= 1: # 球色有剩余\n",
    "             self.当前步数 += 1\n",
    "             self.手上球数[k] -= 1\n",
    "             i = 0\n",
    "             while i <= len(board): # 除了最右端，全部寻找左插入点\n",
    "                # 必须提速：若h和b连续同色则不断跳过; 只有当b两端色大于等于4（RYYRRYYR）且h+b插色大于等于3，才允许插非同色【仅限中间】\n",
    "                if (i>=1 and board[i-1]==k):\n",
    "                   pass\n",
    "                elif i<=len(board)-1 and board[i]!=k and not(1<=i and board[i-1]==board[i] and board.count(board[i])>=4 and v+board.count(k)>=3):\n",
    "                   pass\n",
    "                else:  \n",
    "                  new_board = board[:i]+k+board[i:] if i<=len(board)-1 and board[i]!=k else self.消除连球(board[:i]+k+board[i:], i)\n",
    "                  self.插球(new_board) \n",
    "                i += 1\n",
    "             self.手上球数[k] += 1\n",
    "             self.当前步数 -= 1\n",
    "    def 消除连球(self, board: str, insert_idx: int) -> str:\n",
    "        i = insert_idx\n",
    "        while i<=len(board)-1:\n",
    "            个数 = 1\n",
    "            while i+个数<=len(board)-1 and board[i+个数]==board[i]:\n",
    "                  个数 += 1\n",
    "            if 个数>=3: # 能消除连球\n",
    "               board = self.消除连球(board[:i]+board[i+个数:], 0)\n",
    "               break\n",
    "            i += 个数\n",
    "        return board\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinStep(self, board: str, hand: str) -> int:\n",
    "        def clean(s):\n",
    "            n = 1\n",
    "            while n:\n",
    "                s, n = re.subn(r'(.)\\1{2,}', '', s)\n",
    "            return s\n",
    "        visit = set()\n",
    "        visit.add((board, hand))\n",
    "        index = 0\n",
    "        queue_map = defaultdict(deque)\n",
    "        queue_map[0].append((board, hand))\n",
    "        while True:\n",
    "            if not queue_map[index]:\n",
    "                if index > 5:\n",
    "                    break\n",
    "                index += 1\n",
    "                continue\n",
    "            b, h = queue_map[index].pop()\n",
    "            if not b:\n",
    "                return index if index <= 5 else -1\n",
    "            if not h:\n",
    "                continue\n",
    "            cur = \"*\"\n",
    "            cur_n = 1\n",
    "            for i, v in enumerate(b):\n",
    "                if v == cur:\n",
    "                    # 中间插入一个值， h 中不等于cur的插入一个\n",
    "                    for k in \"RYBGW\":\n",
    "                        if k != cur and k in h and b.count(cur) > 3:\n",
    "                            bk, hk = b[:i] + k + b[i:], h.replace(k, \"\", 1)\n",
    "                            if (bk, hk) not in visit:\n",
    "                                visit.add((bk, hk))\n",
    "                                queue_map[index + 1].append((bk, hk))\n",
    "                    cur_n += 1\n",
    "                    continue\n",
    "                need = 3 - cur_n\n",
    "                if h.count(cur) < need:\n",
    "                    cur = v\n",
    "                    cur_n = 1\n",
    "                    continue\n",
    "                b1, h1 = clean(b[:i] + cur * need + b[i:]), h.replace(cur, \"\", 3 - cur_n)\n",
    "                if (b1, h1) not in visit:\n",
    "                    visit.add((b1, h1))\n",
    "                    queue_map[index + need].append((b1, h1))\n",
    "                cur = v\n",
    "                cur_n = 1\n",
    "            if h.count(cur) >= 3 - cur_n:\n",
    "                b1, h1 = clean(b + cur * (3 - cur_n)), h.replace(cur, \"\", 3 - cur_n)\n",
    "                if (b1, h1) not in visit:\n",
    "                    visit.add((b1, h1))\n",
    "                    queue_map[index + 3 - cur_n].append((b1, h1))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinStep(self, board: str, hand: str) -> int:\n",
    "        def clean(s):\n",
    "            n = 1\n",
    "            while n:\n",
    "                s, n = re.subn(r'(.)\\1{2,}', '', s)\n",
    "            return s\n",
    "        visit = set()\n",
    "        visit.add((board, hand))\n",
    "        index = 0\n",
    "        queue_map = defaultdict(deque)\n",
    "        queue_map[0].append((board, hand))\n",
    "        while True:\n",
    "            if not queue_map[index]:\n",
    "                if index > 5:\n",
    "                    break\n",
    "                index += 1\n",
    "                continue\n",
    "            b, h = queue_map[index].pop()\n",
    "            if not b:\n",
    "                return index if index <= 5 else -1\n",
    "            if not h:\n",
    "                continue\n",
    "            cur = \"*\"\n",
    "            cur_n = 1\n",
    "            for i, v in enumerate(b):\n",
    "                if v == cur:\n",
    "                    # 中间插入一个值， h 中不等于cur的插入一个\n",
    "                    for k in \"RYBGW\":\n",
    "                        if k != cur and k in h and b.count(cur) > 3:\n",
    "                            bk, hk = b[:i] + k + b[i:], h.replace(k, \"\", 1)\n",
    "                            if (bk, hk) not in visit:\n",
    "                                visit.add((bk, hk))\n",
    "                                queue_map[index + 1].append((bk, hk))\n",
    "                    cur_n += 1\n",
    "                    continue\n",
    "                need = 3 - cur_n\n",
    "                if h.count(cur) < need:\n",
    "                    cur = v\n",
    "                    cur_n = 1\n",
    "                    continue\n",
    "                b1, h1 = clean(b[:i] + cur * need + b[i:]), h.replace(cur, \"\", 3 - cur_n)\n",
    "                if (b1, h1) not in visit:\n",
    "                    visit.add((b1, h1))\n",
    "                    queue_map[index + need].append((b1, h1))\n",
    "                cur = v\n",
    "                cur_n = 1\n",
    "            if h.count(cur) >= 3 - cur_n:\n",
    "                b1, h1 = clean(b + cur * (3 - cur_n)), h.replace(cur, \"\", 3 - cur_n)\n",
    "                if (b1, h1) not in visit:\n",
    "                    visit.add((b1, h1))\n",
    "                    queue_map[index + 3 - cur_n].append((b1, h1))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinStep(self, board: str, hand: str) -> int:\n",
    "        # 递归回溯：\n",
    "        # 1.当hand当前位置i之前插入的i-1相同时，是重复操作不要再继续\n",
    "        # 2.当hand当前位置i和之前board前一个位置j-1相同时，说明之前已经尝试过了，不用继续\n",
    "        # 3.当hand位置i放置到board的j位置后，分为三种情况\n",
    "        # 3.1 当hand位置i和board的j位置相同时，可能有最优解\n",
    "        # 3.2 当hand位置i和board的j位置不相等，并且j和j-1位置相同的时候，可能有最有解。\n",
    "        # 3.3 当hand位置i和board的j位置不相等，并且j和j-1位置不相同的时候，不可能有最有解。\n",
    "\n",
    "        def clean(s):\n",
    "            if not s: return ''\n",
    "            n = 1\n",
    "            while n:\n",
    "                s, n = re.subn(r'(.)\\1{2,}', '', s)\n",
    "            return s \n",
    "        hand = ''.join(sorted(hand))\n",
    "        ss = [(board, hand, 0)]\n",
    "        visited = set()\n",
    "        visited.add((board, hand))\n",
    "        while ss:\n",
    "            b, h, s = ss.pop(0)\n",
    "            for i, j in product(range(len(b)+1), range(len(h))):\n",
    "                if j>0 and h[j]==h[j-1]: continue\n",
    "                if i>0 and h[j]==b[i-1]: continue\n",
    "                choose = False\n",
    "\n",
    "                if i<len(b) and b[i]==h[j]: choose = True\n",
    "                if 0<i<len(b) and b[i]==b[i-1] and h[j]!=b[i-1]: choose = True\n",
    "                if choose:\n",
    "                    b1 = clean(b[:i] + h[j] + b[i:])\n",
    "                    h1 = h[:j]+h[j+1:]\n",
    "                    if not b1:\n",
    "                        return s + 1\n",
    "                    if (b1, h1) not in visited:\n",
    "                        ss.append((b1, h1, s+1))\n",
    "                        visited.add((b1, h1))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinStep(self, board: str, hand: str) -> int:\n",
    "        def clean(s):\n",
    "            # 消除桌面上需要消除的球\n",
    "            n = 1\n",
    "            while n:\n",
    "                s, n = re.subn(r\"(.)\\1{2,}\", \"\", s)\n",
    "            return s\n",
    "        hand = \"\".join(sorted(hand))\n",
    "        # 初始化用队列维护的状态队列：其中的三个元素分别为桌面球状态、手中球状态和回合数\n",
    "        queue = deque([(board, hand, 0)])\n",
    "        # 初始化用哈希集合维护的已访问过的状态\n",
    "        visited = {(board, hand)}\n",
    "        while queue:\n",
    "            cur_board, cur_hand, step = queue.popleft()\n",
    "            for i, j in product(range(len(cur_board) + 1), range(len(cur_hand))):\n",
    "                # 第 1 个剪枝条件: 当前球的颜色和上一个球的颜色相同\n",
    "                if j > 0 and cur_hand[j] == cur_hand[j - 1]:\n",
    "                    continue\n",
    "\n",
    "                # 第 2 个剪枝条件: 只在连续相同颜色的球的开头位置插入新球\n",
    "                if i > 0 and cur_board[i - 1] == cur_hand[j]:\n",
    "                    continue\n",
    "                \n",
    "                # 第 3 个剪枝条件: 只在以下两种情况放置新球\n",
    "                choose = False\n",
    "                #  - 第 1 种情况 : 当前球颜色与后面的球的颜色相同\n",
    "                if i < len(cur_board) and cur_board[i] == cur_hand[j]:\n",
    "                    choose = True\n",
    "                #  - 第 2 种情况 : 当前后颜色相同且与当前颜色不同时候放置球\n",
    "                if 0 < i < len(cur_board) and cur_board[i - 1] == cur_board[i] and cur_board[i - 1] != cur_hand[j]:\n",
    "                    choose = True\n",
    "                if choose:\n",
    "                    new_board = clean(cur_board[:i] + cur_hand[j] + cur_board[i:])\n",
    "                    new_hand = cur_hand[:j] + cur_hand[j + 1:]\n",
    "                    if not new_board:\n",
    "                        return step + 1\n",
    "                    if (new_board, new_hand) not in visited:\n",
    "                        queue.append((new_board, new_hand, step + 1))\n",
    "                        visited.add((new_board, new_hand))\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# BFS\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def findMinStep(self, board: str, hand: str) -> int:\n",
    "        def clean(s):\n",
    "            # 消除桌面上需要消除的球\n",
    "            n = 1\n",
    "            while n:\n",
    "                s, n = re.subn(r\"(.)\\1{2,}\", \"\", s)\n",
    "            return s\n",
    "        \n",
    "        hand = \"\".join(sorted(hand))\n",
    "        \n",
    "        # 初始化用队列维护的状态队列，其中的三个元素分别为桌面球状态、手中球状态和回合数\n",
    "        queue = deque([(board, hand, 0)])\n",
    "        \n",
    "        # 初始化用哈希集合维护的已访问过的状态\n",
    "        visited = {(board, hand)}\n",
    "        \n",
    "        while queue:\n",
    "            cur_board, cur_hand, step = queue.popleft()\n",
    "            for i, j in product(range(len(cur_board)+1), range(len(cur_hand))):\n",
    "                # 当前球的颜色与上一个球的颜色相同\n",
    "                if j > 0 and cur_hand[j] == cur_hand[j-1]:\n",
    "                    continue\n",
    "                # 只在连续相同颜色的球的开头位置插入新球\n",
    "                if i > 0 and cur_board[i-1] == cur_hand[j]:\n",
    "                    continue\n",
    "                # 当前球颜色与后面的球的颜色相同或当前后颜色相同且与当前颜色不同时放置球\n",
    "                choose = False\n",
    "                if 0 < i < len(cur_board) and cur_board[i - 1] == cur_board[i] and cur_board[i - 1] != cur_hand[j]:\n",
    "                    choose = True\n",
    "                if i < len(cur_board) and cur_board[i] == cur_hand[j]:\n",
    "                    choose = True\n",
    "                if choose:\n",
    "                    new_board = clean(cur_board[:i]+cur_hand[j]+cur_board[i:])\n",
    "                    new_hand = cur_hand[:j] + cur_hand[j+1:]\n",
    "                    if not new_board:\n",
    "                        return step + 1\n",
    "                    if (new_board, new_hand) not in visited:\n",
    "                        queue.append((new_board, new_hand, step+1))\n",
    "                        visited.add((new_board, new_hand))\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinStep(self, board: str, hand: str) -> int:\n",
    "        def clean(s):\n",
    "            # 消除桌面上需要消除的球\n",
    "            n = 1\n",
    "            while n:\n",
    "                s, n = re.subn(r\"(.)\\1{2,}\", \"\", s)\n",
    "            return s\n",
    "\n",
    "        hand = \"\".join(sorted(hand))\n",
    "\n",
    "        # 初始化用队列维护的状态队列：其中的三个元素分别为桌面球状态、手中球状态和回合数\n",
    "        queue = deque([(board, hand, 0)])\n",
    "\n",
    "        # 初始化用哈希集合维护的已访问过的状态\n",
    "        visited = {(board, hand)}\n",
    "\n",
    "        while queue:\n",
    "            cur_board, cur_hand, step = queue.popleft()\n",
    "            for i, j in product(range(len(cur_board) + 1), range(len(cur_hand))):\n",
    "                # 第 1 个剪枝条件: 当前球的颜色和上一个球的颜色相同\n",
    "                if j > 0 and cur_hand[j] == cur_hand[j - 1]:\n",
    "                    continue\n",
    "\n",
    "                # 第 2 个剪枝条件: 只在连续相同颜色的球的开头位置插入新球\n",
    "                if i > 0 and cur_board[i - 1] == cur_hand[j]:\n",
    "                    continue\n",
    "                \n",
    "                # 第 3 个剪枝条件: 只在以下两种情况放置新球\n",
    "                choose = False\n",
    "                #  - 第 1 种情况 : 当前球颜色与后面的球的颜色相同\n",
    "                if i < len(cur_board) and cur_board[i] == cur_hand[j]:\n",
    "                    choose = True\n",
    "                #  - 第 2 种情况 : 当前后颜色相同且与当前颜色不同时候放置球\n",
    "                if 0 < i < len(cur_board) and cur_board[i - 1] == cur_board[i] and cur_board[i - 1] != cur_hand[j]:\n",
    "                    choose = True\n",
    "\n",
    "                if choose:\n",
    "                    new_board = clean(cur_board[:i] + cur_hand[j] + cur_board[i:])\n",
    "                    new_hand = cur_hand[:j] + cur_hand[j + 1:]\n",
    "                    if not new_board:\n",
    "                        return step + 1\n",
    "                    if (new_board, new_hand) not in visited:\n",
    "                        queue.append((new_board, new_hand, step + 1))\n",
    "                        visited.add((new_board, new_hand))\n",
    "\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinStep(self, board: str, hand: str) -> int:\n",
    "        visited = {(board,hand)}\n",
    "        todo = [(board,hand)]\n",
    "        \n",
    "        def eliminate(content: str):\n",
    "            x = re.search(\"R{3,}|Y{3,}|B{3,}|G{3,}|W{3,}\", content)\n",
    "            while len(content)>0 and x:\n",
    "                content = content[0:x.span()[0]] + content[x.span()[1]:]\n",
    "                x = re.search(\"R{3,}|Y{3,}|B{3,}|G{3,}|W{3,}\", content)\n",
    "            return content\n",
    "\n",
    "        # bfs\n",
    "        while todo:\n",
    "            _board, _hand = todo.pop(0)\n",
    "            for i in range(len(_hand)):\n",
    "                # 手中的相同颜色的球，仅使用一次\n",
    "                if i == _hand.index(_hand[i]):\n",
    "                    for pos in range(len(_board)):\n",
    "                        # 仅插相同颜色的球的左侧，\n",
    "                        if pos > 0 and _board[pos-1] == _hand[i] : continue\n",
    "                        # 左右两边球不同，不能得到更好解\n",
    "                        if pos > 0 and pos < len(_board) and _board[pos] != _hand[i] and _board[pos-1] != _board[pos]: continue\n",
    "                        if pos == 0 and _board[pos] != _hand[i]: continue\n",
    "                        # 其他可以得到更优解的情况\n",
    "                        inserted = eliminate(_board[0:pos]+_hand[i]+_board[pos:])\n",
    "                        if inserted == \"\":\n",
    "                            return len(hand) - len(_hand) + 1\n",
    "                        if (inserted, _hand[0:i]+_hand[i+1:]) not in visited:\n",
    "                            visited.add((inserted, _hand[0:i]+_hand[i+1:]))\n",
    "                            todo.append((inserted, _hand[0:i]+_hand[i+1:]))\n",
    "                            \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinStep(self, board: str, hand: str) -> int:\n",
    "        def clean(s):\n",
    "            # 消除桌面上需要消除的球\n",
    "            n = 1\n",
    "            while n:\n",
    "                s, n = re.subn(r\"(.)\\1{2,}\", \"\", s)\n",
    "            return s\n",
    "        hand = \"\".join(sorted(hand))\n",
    "        # 初始化用队列维护的状态队列：其中的三个元素分别为桌面球状态、手中球状态和回合数\n",
    "        queue = deque([(board, hand, 0)])\n",
    "        # 初始化用哈希集合维护的已访问过的状态\n",
    "        visited = {(board, hand)}\n",
    "        while queue:\n",
    "            cur_board, cur_hand, step = queue.popleft()\n",
    "            for i, j in product(range(len(cur_board) + 1), range(len(cur_hand))):\n",
    "                # 第 1 个剪枝条件: 当前球的颜色和上一个球的颜色相同\n",
    "                if j > 0 and cur_hand[j] == cur_hand[j - 1]:\n",
    "                    continue\n",
    "                # 第 2 个剪枝条件: 只在连续相同颜色的球的开头位置插入新球\n",
    "                if i > 0 and cur_board[i - 1] == cur_hand[j]:\n",
    "                    continue\n",
    "                # 第 3 个剪枝条件: 只在以下两种情况放置新球\n",
    "                choose = False\n",
    "                #  - 第 1 种情况 : 当前球颜色与后面的球的颜色相同\n",
    "                if i < len(cur_board) and cur_board[i] == cur_hand[j]:\n",
    "                    choose = True\n",
    "                #  - 第 2 种情况 : 当前后颜色相同且与当前颜色不同时候放置球\n",
    "                if 0 < i < len(cur_board) and cur_board[i - 1] == cur_board[i] and cur_board[i - 1] != cur_hand[j]:\n",
    "                    choose = True\n",
    "                if choose:\n",
    "                    new_board = clean(cur_board[:i] + cur_hand[j] + cur_board[i:])\n",
    "                    new_hand = cur_hand[:j] + cur_hand[j + 1:]\n",
    "                    if not new_board:\n",
    "                        return step + 1\n",
    "                    if (new_board, new_hand) not in visited:\n",
    "                        queue.append((new_board, new_hand, step + 1))\n",
    "                        visited.add((new_board, new_hand))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinStep(self, board: str, hand: str) -> int:\n",
    "        def clean(s):\n",
    "            # 消除桌面上需要消除的球\n",
    "            n = 1\n",
    "            while n:\n",
    "                s, n = re.subn(r\"(.)\\1{2,}\", \"\", s)\n",
    "            return s\n",
    "\n",
    "        hand = \"\".join(sorted(hand))\n",
    "\n",
    "        # 初始化用队列维护的状态队列：其中的三个元素分别为桌面球状态、手中球状态和回合数\n",
    "        queue = deque([(board, hand, 0)])\n",
    "\n",
    "        # 初始化用哈希集合维护的已访问过的状态\n",
    "        visited = {(board, hand)}\n",
    "\n",
    "        while queue:\n",
    "            cur_board, cur_hand, step = queue.popleft()\n",
    "            for i, j in product(range(len(cur_board) + 1), range(len(cur_hand))):\n",
    "                # 第 1 个剪枝条件: 当前球的颜色和上一个球的颜色相同\n",
    "                if j > 0 and cur_hand[j] == cur_hand[j - 1]:\n",
    "                    continue\n",
    "\n",
    "                # 第 2 个剪枝条件: 只在连续相同颜色的球的开头位置插入新球\n",
    "                if i > 0 and cur_board[i - 1] == cur_hand[j]:\n",
    "                    continue\n",
    "                \n",
    "                # 第 3 个剪枝条件: 只在以下两种情况放置新球\n",
    "                choose = False\n",
    "                #  - 第 1 种情况 : 当前球颜色与后面的球的颜色相同\n",
    "                if i < len(cur_board) and cur_board[i] == cur_hand[j]:\n",
    "                    choose = True\n",
    "                #  - 第 2 种情况 : 当前后颜色相同且与当前颜色不同时候放置球\n",
    "                if 0 < i < len(cur_board) and cur_board[i - 1] == cur_board[i] and cur_board[i - 1] != cur_hand[j]:\n",
    "                    choose = True\n",
    "\n",
    "                if choose:\n",
    "                    new_board = clean(cur_board[:i] + cur_hand[j] + cur_board[i:])\n",
    "                    new_hand = cur_hand[:j] + cur_hand[j + 1:]\n",
    "                    if not new_board:\n",
    "                        return step + 1\n",
    "                    if (new_board, new_hand) not in visited:\n",
    "                        queue.append((new_board, new_hand, step + 1))\n",
    "                        visited.add((new_board, new_hand))\n",
    "\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinStep(self, board: str, hand: str) -> int:\n",
    "        def clean(s):\n",
    "            # 消除桌面上需要消除的球\n",
    "            n = 1\n",
    "            while n:\n",
    "                s, n = re.subn(r\"(.)\\1{2,}\", \"\", s)\n",
    "            return s\n",
    "        hand = \"\".join(sorted(hand))\n",
    "        # 初始化用队列维护的状态队列：其中的三个元素分别为桌面球状态、手中球状态和回合数\n",
    "        queue = deque([(board, hand, 0)])\n",
    "        # 初始化用哈希集合维护的已访问过的状态\n",
    "        visited = {(board, hand)}\n",
    "        while queue:\n",
    "            cur_board, cur_hand, step = queue.popleft()\n",
    "            for i, j in product(range(len(cur_board) + 1), range(len(cur_hand))):\n",
    "                # 第 1 个剪枝条件: 当前球的颜色和上一个球的颜色相同\n",
    "                if j > 0 and cur_hand[j] == cur_hand[j - 1]:\n",
    "                    continue\n",
    "\n",
    "                # 第 2 个剪枝条件: 只在连续相同颜色的球的开头位置插入新球\n",
    "                if i > 0 and cur_board[i - 1] == cur_hand[j]:\n",
    "                    continue\n",
    "                \n",
    "                # 第 3 个剪枝条件: 只在以下两种情况放置新球\n",
    "                choose = False\n",
    "                #  - 第 1 种情况 : 当前球颜色与后面的球的颜色相同\n",
    "                if i < len(cur_board) and cur_board[i] == cur_hand[j]:\n",
    "                    choose = True\n",
    "                #  - 第 2 种情况 : 当前后颜色相同且与当前颜色不同时候放置球\n",
    "                if 0 < i < len(cur_board) and cur_board[i - 1] == cur_board[i] and cur_board[i - 1] != cur_hand[j]:\n",
    "                    choose = True\n",
    "                if choose:\n",
    "                    new_board = clean(cur_board[:i] + cur_hand[j] + cur_board[i:])\n",
    "                    new_hand = cur_hand[:j] + cur_hand[j + 1:]\n",
    "                    if not new_board:\n",
    "                        return step + 1\n",
    "                    if (new_board, new_hand) not in visited:\n",
    "                        queue.append((new_board, new_hand, step + 1))\n",
    "                        visited.add((new_board, new_hand))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinStep(self, board: str, hand: str) -> int:\n",
    "        def clean(s: str):\n",
    "            n = 1\n",
    "            while n:\n",
    "                s, n = re.subn(r\"(.)\\1{2,}\", \"\", s)\n",
    "            return s\n",
    "        hand = \"\".join(sorted(hand))\n",
    "        queue = deque([(board, hand, 0)])\n",
    "        visited = {(board, hand)}\n",
    "        while queue:\n",
    "            cur_board, cur_hand, step = queue.popleft()\n",
    "            for i, j in itertools.product(range(len(cur_board)), range(len(cur_hand))):\n",
    "                # cut:\n",
    "                # 1. if several identical color balls in hand, then only choose one\n",
    "                if j > 0 and cur_hand[j] == cur_hand[j - 1]:\n",
    "                    continue\n",
    "                # 2. only add ball in front of consecutive balls\n",
    "                if i > 0 and cur_board[i - 1] == cur_hand[j]:\n",
    "                    continue\n",
    "                # 3. only in below two condition that balls in hand can be added to board\n",
    "                choose = False\n",
    "                # 3.1 the ball has the same color as the later ball in board\n",
    "                if cur_hand[j] == cur_board[i]:\n",
    "                    choose = True\n",
    "                # 3.2 the ball has different color with the later ball and the ahead ball but the later ball and ahead ball\n",
    "                # have the same color\n",
    "                if i > 0 and cur_board[i] == cur_board[i - 1] and cur_hand[j] != cur_board[i]:\n",
    "                    choose = True\n",
    "\n",
    "                if choose:\n",
    "                    new_board = clean(cur_board[:i] + cur_hand[j] + cur_board[i:])\n",
    "                    new_hand = cur_hand[:j] + cur_hand[j + 1:]\n",
    "                    if not new_board:\n",
    "                        return step + 1\n",
    "                    if (new_board, new_hand) not in visited:\n",
    "                        queue.append((new_board, new_hand, step + 1))\n",
    "                        visited.add((new_board, new_hand))\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinStep(self, board: str, hand: str) -> int:\n",
    "        def clean(s):\n",
    "            # 消除桌面上需要消除的球\n",
    "            n = 1\n",
    "            while n:\n",
    "                s, n = re.subn(r\"(.)\\1{2,}\", \"\", s)\n",
    "            return s\n",
    "\n",
    "        hand = \"\".join(sorted(hand))\n",
    "\n",
    "        # 初始化用队列维护的状态队列：其中的三个元素分别为桌面球状态、手中球状态和回合数\n",
    "        queue = deque([(board, hand, 0)])\n",
    "\n",
    "        # 初始化用哈希集合维护的已访问过的状态\n",
    "        visited = {(board, hand)}\n",
    "\n",
    "        while queue:\n",
    "            cur_board, cur_hand, step = queue.popleft()\n",
    "            for i, j in product(range(len(cur_board) + 1), range(len(cur_hand))):\n",
    "                # 第 1 个剪枝条件: 当前球的颜色和上一个球的颜色相同\n",
    "                if j > 0 and cur_hand[j] == cur_hand[j - 1]:\n",
    "                    continue\n",
    "\n",
    "                # 第 2 个剪枝条件: 只在连续相同颜色的球的开头位置插入新球\n",
    "                if i > 0 and cur_board[i - 1] == cur_hand[j]:\n",
    "                    continue\n",
    "                \n",
    "                # 第 3 个剪枝条件: 只在以下两种情况放置新球\n",
    "                choose = False\n",
    "                #  - 第 1 种情况 : 当前球颜色与后面的球的颜色相同\n",
    "                if i < len(cur_board) and cur_board[i] == cur_hand[j]:\n",
    "                    choose = True\n",
    "                #  - 第 2 种情况 : 当前后颜色相同且与当前颜色不同时候放置球\n",
    "                if 0 < i < len(cur_board) and cur_board[i - 1] == cur_board[i] and cur_board[i - 1] != cur_hand[j]:\n",
    "                    choose = True\n",
    "\n",
    "                if choose:\n",
    "                    new_board = clean(cur_board[:i] + cur_hand[j] + cur_board[i:])\n",
    "                    new_hand = cur_hand[:j] + cur_hand[j + 1:]\n",
    "                    if not new_board:\n",
    "                        return step + 1\n",
    "                    if (new_board, new_hand) not in visited:\n",
    "                        queue.append((new_board, new_hand, step + 1))\n",
    "                        visited.add((new_board, new_hand))\n",
    "\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinStep(self, board: str, hand: str) -> int:\n",
    "        def clean(s):\n",
    "            # 消除桌面上需要消除的球\n",
    "            n = 1\n",
    "            while n:\n",
    "                s, n = re.subn(r\"(.)\\1{2,}\", \"\", s)\n",
    "            return s\n",
    "\n",
    "        hand = \"\".join(sorted(hand))\n",
    "\n",
    "        # 初始化用队列维护的状态队列：其中的三个元素分别为桌面球状态、手中球状态和回合数\n",
    "        queue = deque([(board, hand, 0)])\n",
    "\n",
    "        # 初始化用哈希集合维护的已访问过的状态\n",
    "        visited = {(board, hand)}\n",
    "\n",
    "        while queue:\n",
    "            cur_board, cur_hand, step = queue.popleft()\n",
    "            for i, j in product(range(len(cur_board) + 1), range(len(cur_hand))):\n",
    "                # 第 1 个剪枝条件: 当前球的颜色和上一个球的颜色相同\n",
    "                if j > 0 and cur_hand[j] == cur_hand[j - 1]:\n",
    "                    continue\n",
    "\n",
    "                # 第 2 个剪枝条件: 只在连续相同颜色的球的开头位置插入新球\n",
    "                if i > 0 and cur_board[i - 1] == cur_hand[j]:\n",
    "                    continue\n",
    "                \n",
    "                # 第 3 个剪枝条件: 只在以下两种情况放置新球\n",
    "                choose = False\n",
    "                #  - 第 1 种情况 : 当前球颜色与后面的球的颜色相同\n",
    "                if i < len(cur_board) and cur_board[i] == cur_hand[j]:\n",
    "                    choose = True\n",
    "                #  - 第 2 种情况 : 当前后颜色相同且与当前颜色不同时候放置球\n",
    "                if 0 < i < len(cur_board) and cur_board[i - 1] == cur_board[i] and cur_board[i - 1] != cur_hand[j]:\n",
    "                    choose = True\n",
    "\n",
    "                if choose:\n",
    "                    new_board = clean(cur_board[:i] + cur_hand[j] + cur_board[i:])\n",
    "                    new_hand = cur_hand[:j] + cur_hand[j + 1:]\n",
    "                    if not new_board:\n",
    "                        return step + 1\n",
    "                    if (new_board, new_hand) not in visited:\n",
    "                        queue.append((new_board, new_hand, step + 1))\n",
    "                        visited.add((new_board, new_hand))\n",
    "\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinStep(self, board: str, hand: str) -> int:\n",
    "        def clean(s):\n",
    "            # 消除桌面上需要消除的球\n",
    "            n = 1\n",
    "            while n:\n",
    "                s, n = re.subn(r\"(.)\\1{2,}\", \"\", s)\n",
    "            return s\n",
    "\n",
    "        hand = \"\".join(sorted(hand))\n",
    "\n",
    "        # 初始化用队列维护的状态队列：其中的三个元素分别为桌面球状态、手中球状态和回合数\n",
    "        queue = deque([(board, hand, 0)])\n",
    "\n",
    "        # 初始化用哈希集合维护的已访问过的状态\n",
    "        visited = {(board, hand)}\n",
    "\n",
    "        while queue:\n",
    "            cur_board, cur_hand, step = queue.popleft()\n",
    "            for i, j in product(range(len(cur_board) + 1), range(len(cur_hand))):\n",
    "                # 第 1 个剪枝条件: 当前球的颜色和上一个球的颜色相同\n",
    "                if j > 0 and cur_hand[j] == cur_hand[j - 1]:\n",
    "                    continue\n",
    "\n",
    "                # 第 2 个剪枝条件: 只在连续相同颜色的球的开头位置插入新球\n",
    "                if i > 0 and cur_board[i - 1] == cur_hand[j]:\n",
    "                    continue\n",
    "                \n",
    "                # 第 3 个剪枝条件: 只在以下两种情况放置新球\n",
    "                choose = False\n",
    "                #  - 第 1 种情况 : 当前球颜色与后面的球的颜色相同\n",
    "                if i < len(cur_board) and cur_board[i] == cur_hand[j]:\n",
    "                    choose = True\n",
    "                #  - 第 2 种情况 : 当前后颜色相同且与当前颜色不同时候放置球\n",
    "                if 0 < i < len(cur_board) and cur_board[i - 1] == cur_board[i] and cur_board[i - 1] != cur_hand[j]:\n",
    "                    choose = True\n",
    "\n",
    "                if choose:\n",
    "                    new_board = clean(cur_board[:i] + cur_hand[j] + cur_board[i:])\n",
    "                    new_hand = cur_hand[:j] + cur_hand[j + 1:]\n",
    "                    if not new_board:\n",
    "                        return step + 1\n",
    "                    if (new_board, new_hand) not in visited:\n",
    "                        queue.append((new_board, new_hand, step + 1))\n",
    "                        visited.add((new_board, new_hand))\n",
    "\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinStep(self, board: str, hand: str) -> int:\n",
    "        def clean(s):\n",
    "            # 消除桌面上需要消除的球\n",
    "            n = 1\n",
    "            while n:\n",
    "                s, n = re.subn(r\"(.)\\1{2,}\", \"\", s)\n",
    "            return s\n",
    "\n",
    "        hand = \"\".join(sorted(hand))\n",
    "\n",
    "        # 初始化用队列维护的状态队列：其中的三个元素分别为桌面球状态、手中球状态和回合数\n",
    "        queue = deque([(board, hand, 0)])\n",
    "\n",
    "        # 初始化用哈希集合维护的已访问过的状态\n",
    "        visited = {(board, hand)}\n",
    "\n",
    "        while queue:\n",
    "            cur_board, cur_hand, step = queue.popleft()\n",
    "            for i, j in product(range(len(cur_board) + 1), range(len(cur_hand))):\n",
    "                # 第 1 个剪枝条件: 当前球的颜色和上一个球的颜色相同\n",
    "                if j > 0 and cur_hand[j] == cur_hand[j - 1]:\n",
    "                    continue\n",
    "\n",
    "                # 第 2 个剪枝条件: 只在连续相同颜色的球的开头位置插入新球\n",
    "                if i > 0 and cur_board[i - 1] == cur_hand[j]:\n",
    "                    continue\n",
    "                \n",
    "                # 第 3 个剪枝条件: 只在以下两种情况放置新球\n",
    "                choose = False\n",
    "                #  - 第 1 种情况 : 当前球颜色与后面的球的颜色相同\n",
    "                if i < len(cur_board) and cur_board[i] == cur_hand[j]:\n",
    "                    choose = True\n",
    "                #  - 第 2 种情况 : 当前后颜色相同且与当前颜色不同时候放置球\n",
    "                if 0 < i < len(cur_board) and cur_board[i - 1] == cur_board[i] and cur_board[i - 1] != cur_hand[j]:\n",
    "                    choose = True\n",
    "\n",
    "                if choose:\n",
    "                    new_board = clean(cur_board[:i] + cur_hand[j] + cur_board[i:])\n",
    "                    new_hand = cur_hand[:j] + cur_hand[j + 1:]\n",
    "                    if not new_board:\n",
    "                        return step + 1\n",
    "                    if (new_board, new_hand) not in visited:\n",
    "                        queue.append((new_board, new_hand, step + 1))\n",
    "                        visited.add((new_board, new_hand))\n",
    "\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinStep(self, board: str, hand: str) -> int:\n",
    "        def clean(s):\n",
    "            # 消除桌面上需要消除的球\n",
    "            n = 1\n",
    "            while n:\n",
    "                s, n = re.subn(r\"(.)\\1{2,}\", \"\", s)\n",
    "            return s\n",
    "\n",
    "        hand = \"\".join(sorted(hand))\n",
    "\n",
    "        # 初始化用队列维护的状态队列：其中的三个元素分别为桌面球状态、手中球状态和回合数\n",
    "        queue = deque([(board, hand, 0)])\n",
    "\n",
    "        # 初始化用哈希集合维护的已访问过的状态\n",
    "        visited = {(board, hand)}\n",
    "\n",
    "        while queue:\n",
    "            cur_board, cur_hand, step = queue.popleft()\n",
    "            for i, j in product(range(len(cur_board) + 1), range(len(cur_hand))):\n",
    "                # 第 1 个剪枝条件: 当前球的颜色和上一个球的颜色相同\n",
    "                if j > 0 and cur_hand[j] == cur_hand[j - 1]:\n",
    "                    continue\n",
    "\n",
    "                # 第 2 个剪枝条件: 只在连续相同颜色的球的开头位置插入新球\n",
    "                if i > 0 and cur_board[i - 1] == cur_hand[j]:\n",
    "                    continue\n",
    "                \n",
    "                # 第 3 个剪枝条件: 只在以下两种情况放置新球\n",
    "                choose = False\n",
    "                #  - 第 1 种情况 : 当前球颜色与后面的球的颜色相同\n",
    "                if i < len(cur_board) and cur_board[i] == cur_hand[j]:\n",
    "                    choose = True\n",
    "                #  - 第 2 种情况 : 当前后颜色相同且与当前颜色不同时候放置球\n",
    "                if 0 < i < len(cur_board) and cur_board[i - 1] == cur_board[i] and cur_board[i - 1] != cur_hand[j]:\n",
    "                    choose = True\n",
    "\n",
    "                if choose:\n",
    "                    new_board = clean(cur_board[:i] + cur_hand[j] + cur_board[i:])\n",
    "                    new_hand = cur_hand[:j] + cur_hand[j + 1:]\n",
    "                    if not new_board:\n",
    "                        return step + 1\n",
    "                    if (new_board, new_hand) not in visited:\n",
    "                        queue.append((new_board, new_hand, step + 1))\n",
    "                        visited.add((new_board, new_hand))\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinStep(self, board: str, hand: str) -> int:\n",
    "        def clean(s):\n",
    "            # 消除桌面上需要消除的球\n",
    "            n = 1\n",
    "            while n:\n",
    "                s, n = re.subn(r\"(.)\\1{2,}\", \"\", s)\n",
    "            return s\n",
    "\n",
    "        hand = \"\".join(sorted(hand))\n",
    "\n",
    "        # 初始化用队列维护的状态队列：其中的三个元素分别为桌面球状态、手中球状态和回合数\n",
    "        queue = deque([(board, hand, 0)])\n",
    "\n",
    "        # 初始化用哈希集合维护的已访问过的状态\n",
    "        visited = {(board, hand)}\n",
    "\n",
    "        while queue:\n",
    "            cur_board, cur_hand, step = queue.popleft()\n",
    "            for i, j in product(range(len(cur_board) + 1), range(len(cur_hand))):\n",
    "                # 第 1 个剪枝条件: 当前球的颜色和上一个球的颜色相同\n",
    "                if j > 0 and cur_hand[j] == cur_hand[j - 1]:\n",
    "                    continue\n",
    "\n",
    "                # 第 2 个剪枝条件: 只在连续相同颜色的球的开头位置插入新球\n",
    "                if i > 0 and cur_board[i - 1] == cur_hand[j]:\n",
    "                    continue\n",
    "                \n",
    "                # 第 3 个剪枝条件: 只在以下两种情况放置新球\n",
    "                choose = False\n",
    "                #  - 第 1 种情况 : 当前球颜色与后面的球的颜色相同\n",
    "                if i < len(cur_board) and cur_board[i] == cur_hand[j]:\n",
    "                    choose = True\n",
    "                #  - 第 2 种情况 : 当前后颜色相同且与当前颜色不同时候放置球\n",
    "                if 0 < i < len(cur_board) and cur_board[i - 1] == cur_board[i] and cur_board[i - 1] != cur_hand[j]:\n",
    "                    choose = True\n",
    "\n",
    "                if choose:\n",
    "                    new_board = clean(cur_board[:i] + cur_hand[j] + cur_board[i:])\n",
    "                    new_hand = cur_hand[:j] + cur_hand[j + 1:]\n",
    "                    if not new_board:\n",
    "                        return step + 1\n",
    "                    if (new_board, new_hand) not in visited:\n",
    "                        queue.append((new_board, new_hand, step + 1))\n",
    "                        visited.add((new_board, new_hand))\n",
    "\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinStep(self, board: str, hand: str) -> int:\n",
    "        def clean(s):\n",
    "            # 消除桌面上需要消除的球\n",
    "            n = 1\n",
    "            while n:\n",
    "                s, n = re.subn(r\"(.)\\1{2,}\", \"\", s)\n",
    "            return s\n",
    "\n",
    "        hand = \"\".join(sorted(hand))\n",
    "\n",
    "        # 初始化用队列维护的状态队列：其中的三个元素分别为桌面球状态、手中球状态和回合数\n",
    "        queue = deque([(board, hand, 0)])\n",
    "\n",
    "        # 初始化用哈希集合维护的已访问过的状态\n",
    "        visited = {(board, hand)}\n",
    "\n",
    "        while queue:\n",
    "            cur_board, cur_hand, step = queue.popleft()\n",
    "            for i, j in product(range(len(cur_board) + 1), range(len(cur_hand))):\n",
    "                # 第 1 个剪枝条件: 当前球的颜色和上一个球的颜色相同\n",
    "                if j > 0 and cur_hand[j] == cur_hand[j - 1]:\n",
    "                    continue\n",
    "\n",
    "                # 第 2 个剪枝条件: 只在连续相同颜色的球的开头位置插入新球\n",
    "                if i > 0 and cur_board[i - 1] == cur_hand[j]:\n",
    "                    continue\n",
    "                \n",
    "                # 第 3 个剪枝条件: 只在以下两种情况放置新球\n",
    "                choose = False\n",
    "                #  - 第 1 种情况 : 当前球颜色与后面的球的颜色相同\n",
    "                if i < len(cur_board) and cur_board[i] == cur_hand[j]:\n",
    "                    choose = True\n",
    "                #  - 第 2 种情况 : 当前后颜色相同且与当前颜色不同时候放置球\n",
    "                if 0 < i < len(cur_board) and cur_board[i - 1] == cur_board[i] and cur_board[i - 1] != cur_hand[j]:\n",
    "                    choose = True\n",
    "\n",
    "                if choose:\n",
    "                    new_board = clean(cur_board[:i] + cur_hand[j] + cur_board[i:])\n",
    "                    new_hand = cur_hand[:j] + cur_hand[j + 1:]\n",
    "                    if not new_board:\n",
    "                        return step + 1\n",
    "                    if (new_board, new_hand) not in visited:\n",
    "                        queue.append((new_board, new_hand, step + 1))\n",
    "                        visited.add((new_board, new_hand))\n",
    "\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinStep(self, board: str, hand: str) -> int:\n",
    "        def clean(s):\n",
    "            # 消除桌面上需要消除的球\n",
    "            n = 1\n",
    "            while n:\n",
    "                s, n = re.subn(r\"(.)\\1{2,}\", \"\", s)\n",
    "            return s\n",
    "\n",
    "        hand = \"\".join(sorted(hand))\n",
    "\n",
    "        # 初始化用队列维护的状态队列：其中的三个元素分别为桌面球状态、手中球状态和回合数\n",
    "        queue = deque([(board, hand, 0)])\n",
    "\n",
    "        # 初始化用哈希集合维护的已访问过的状态\n",
    "        visited = {(board, hand)}\n",
    "\n",
    "        while queue:\n",
    "            cur_board, cur_hand, step = queue.popleft()\n",
    "            for i, j in product(range(len(cur_board) + 1), range(len(cur_hand))):\n",
    "                # 第 1 个剪枝条件: 当前球的颜色和上一个球的颜色相同\n",
    "                if j > 0 and cur_hand[j] == cur_hand[j - 1]:\n",
    "                    continue\n",
    "\n",
    "                # 第 2 个剪枝条件: 只在连续相同颜色的球的开头位置插入新球\n",
    "                if i > 0 and cur_board[i - 1] == cur_hand[j]:\n",
    "                    continue\n",
    "                \n",
    "                # 第 3 个剪枝条件: 只在以下两种情况放置新球\n",
    "                choose = False\n",
    "                #  - 第 1 种情况 : 当前球颜色与后面的球的颜色相同\n",
    "                if i < len(cur_board) and cur_board[i] == cur_hand[j]:\n",
    "                    choose = True\n",
    "                #  - 第 2 种情况 : 当前后颜色相同且与当前颜色不同时候放置球\n",
    "                if 0 < i < len(cur_board) and cur_board[i - 1] == cur_board[i] and cur_board[i - 1] != cur_hand[j]:\n",
    "                    choose = True\n",
    "\n",
    "                if choose:\n",
    "                    new_board = clean(cur_board[:i] + cur_hand[j] + cur_board[i:])\n",
    "                    new_hand = cur_hand[:j] + cur_hand[j + 1:]\n",
    "                    if not new_board:\n",
    "                        return step + 1\n",
    "                    if (new_board, new_hand) not in visited:\n",
    "                        queue.append((new_board, new_hand, step + 1))\n",
    "                        visited.add((new_board, new_hand))\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinStep(self, board: str, hand: str) -> int:\n",
    "        def clean(s):\n",
    "            # 消除桌面上需要消除的球\n",
    "            n = 1\n",
    "            while n:\n",
    "                s, n = re.subn(r\"(.)\\1{2,}\", \"\", s)\n",
    "            return s\n",
    "\n",
    "        hand = \"\".join(sorted(hand))\n",
    "\n",
    "        # 初始化用队列维护的状态队列：其中的三个元素分别为桌面球状态、手中球状态和回合数\n",
    "        queue = deque([(board, hand, 0)])\n",
    "\n",
    "        # 初始化用哈希集合维护的已访问过的状态\n",
    "        visited = {(board, hand)}\n",
    "\n",
    "        while queue:\n",
    "            cur_board, cur_hand, step = queue.popleft()\n",
    "            for i, j in product(range(len(cur_board) + 1), range(len(cur_hand))):\n",
    "                # 第 1 个剪枝条件: 当前球的颜色和上一个球的颜色相同\n",
    "                if j > 0 and cur_hand[j] == cur_hand[j - 1]:\n",
    "                    continue\n",
    "\n",
    "                # 第 2 个剪枝条件: 只在连续相同颜色的球的开头位置插入新球\n",
    "                if i > 0 and cur_board[i - 1] == cur_hand[j]:\n",
    "                    continue\n",
    "                \n",
    "                # 第 3 个剪枝条件: 只在以下两种情况放置新球\n",
    "                choose = False\n",
    "                #  - 第 1 种情况 : 当前球颜色与后面的球的颜色相同\n",
    "                if i < len(cur_board) and cur_board[i] == cur_hand[j]:\n",
    "                    choose = True\n",
    "                #  - 第 2 种情况 : 当前后颜色相同且与当前颜色不同时候放置球\n",
    "                if 0 < i < len(cur_board) and cur_board[i - 1] == cur_board[i] and cur_board[i - 1] != cur_hand[j]:\n",
    "                    choose = True\n",
    "\n",
    "                if choose:\n",
    "                    new_board = clean(cur_board[:i] + cur_hand[j] + cur_board[i:])\n",
    "                    new_hand = cur_hand[:j] + cur_hand[j + 1:]\n",
    "                    if not new_board:\n",
    "                        return step + 1\n",
    "                    if (new_board, new_hand) not in visited:\n",
    "                        queue.append((new_board, new_hand, step + 1))\n",
    "                        visited.add((new_board, new_hand))\n",
    "\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinStep(self, board: str, hand: str) -> int:\n",
    "        def clean(s):\n",
    "            # 消除桌面上需要消除的球\n",
    "            n = 1\n",
    "            while n:\n",
    "                s, n = re.subn(r\"(.)\\1{2,}\", \"\", s)\n",
    "            return s\n",
    "\n",
    "        hand = \"\".join(sorted(hand))\n",
    "\n",
    "        # 初始化用队列维护的状态队列：其中的三个元素分别为桌面球状态、手中球状态和回合数\n",
    "        queue = deque([(board, hand, 0)])\n",
    "\n",
    "        # 初始化用哈希集合维护的已访问过的状态\n",
    "        visited = {(board, hand)}\n",
    "\n",
    "        while queue:\n",
    "            cur_board, cur_hand, step = queue.popleft()\n",
    "            for i, j in product(range(len(cur_board) + 1), range(len(cur_hand))):\n",
    "                # 第 1 个剪枝条件: 当前球的颜色和上一个球的颜色相同\n",
    "                if j > 0 and cur_hand[j] == cur_hand[j - 1]:\n",
    "                    continue\n",
    "\n",
    "                # 第 2 个剪枝条件: 只在连续相同颜色的球的开头位置插入新球\n",
    "                if i > 0 and cur_board[i - 1] == cur_hand[j]:\n",
    "                    continue\n",
    "                \n",
    "                # 第 3 个剪枝条件: 只在以下两种情况放置新球\n",
    "                choose = False\n",
    "                #  - 第 1 种情况 : 当前球颜色与后面的球的颜色相同\n",
    "                if i < len(cur_board) and cur_board[i] == cur_hand[j]:\n",
    "                    choose = True\n",
    "                #  - 第 2 种情况 : 当前后颜色相同且与当前颜色不同时候放置球\n",
    "                if 0 < i < len(cur_board) and cur_board[i - 1] == cur_board[i] and cur_board[i - 1] != cur_hand[j]:\n",
    "                    choose = True\n",
    "\n",
    "                if choose:\n",
    "                    new_board = clean(cur_board[:i] + cur_hand[j] + cur_board[i:])\n",
    "                    new_hand = cur_hand[:j] + cur_hand[j + 1:]\n",
    "                    if not new_board:\n",
    "                        return step + 1\n",
    "                    if (new_board, new_hand) not in visited:\n",
    "                        queue.append((new_board, new_hand, step + 1))\n",
    "                        visited.add((new_board, new_hand))\n",
    "\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinStep(self, board: str, hand: str) -> int:\n",
    "        def clean(s):\n",
    "            # 消除桌面上需要消除的球\n",
    "            n = 1\n",
    "            while n:\n",
    "                s, n = re.subn(r\"(.)\\1{2,}\", \"\", s)\n",
    "            return s\n",
    "\n",
    "        hand = \"\".join(sorted(hand))\n",
    "\n",
    "        # 初始化用队列维护的状态队列：其中的三个元素分别为桌面球状态、手中球状态和回合数\n",
    "        queue = deque([(board, hand, 0)])\n",
    "\n",
    "        # 初始化用哈希集合维护的已访问过的状态\n",
    "        visited = {(board, hand)}\n",
    "\n",
    "        while queue:\n",
    "            cur_board, cur_hand, step = queue.popleft()\n",
    "            for i, j in product(range(len(cur_board) + 1), range(len(cur_hand))):\n",
    "                # 第 1 个剪枝条件: 当前球的颜色和上一个球的颜色相同\n",
    "                if j > 0 and cur_hand[j] == cur_hand[j - 1]:\n",
    "                    continue\n",
    "\n",
    "                # 第 2 个剪枝条件: 只在连续相同颜色的球的开头位置插入新球\n",
    "                if i > 0 and cur_board[i - 1] == cur_hand[j]:\n",
    "                    continue\n",
    "                \n",
    "                # 第 3 个剪枝条件: 只在以下两种情况放置新球\n",
    "                choose = False\n",
    "                #  - 第 1 种情况 : 当前球颜色与后面的球的颜色相同\n",
    "                if i < len(cur_board) and cur_board[i] == cur_hand[j]:\n",
    "                    choose = True\n",
    "                #  - 第 2 种情况 : 当前后颜色相同且与当前颜色不同时候放置球\n",
    "                if 0 < i < len(cur_board) and cur_board[i - 1] == cur_board[i] and cur_board[i - 1] != cur_hand[j]:\n",
    "                    choose = True\n",
    "\n",
    "                if choose:\n",
    "                    new_board = clean(cur_board[:i] + cur_hand[j] + cur_board[i:])\n",
    "                    new_hand = cur_hand[:j] + cur_hand[j + 1:]\n",
    "                    if not new_board:\n",
    "                        return step + 1\n",
    "                    if (new_board, new_hand) not in visited:\n",
    "                        queue.append((new_board, new_hand, step + 1))\n",
    "                        visited.add((new_board, new_hand))\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinStep(self, board: str, hand: str) -> int:\n",
    "        def clean(s):\n",
    "            # 消除桌面上需要消除的球\n",
    "            n = 1\n",
    "            while n:\n",
    "                s, n = re.subn(r\"(.)\\1{2,}\", \"\", s)\n",
    "            return s\n",
    "\n",
    "        hand = \"\".join(sorted(hand))\n",
    "\n",
    "        # 初始化用队列维护的状态队列：其中的三个元素分别为桌面球状态、手中球状态和回合数\n",
    "        queue = deque([(board, hand, 0)])\n",
    "\n",
    "        # 初始化用哈希集合维护的已访问过的状态\n",
    "        visited = {(board, hand)}\n",
    "\n",
    "        while queue:\n",
    "            cur_board, cur_hand, step = queue.popleft()\n",
    "            for i, j in product(range(len(cur_board) + 1), range(len(cur_hand))):\n",
    "                # 第 1 个剪枝条件: 当前球的颜色和上一个球的颜色相同\n",
    "                if j > 0 and cur_hand[j] == cur_hand[j - 1]:\n",
    "                    continue\n",
    "\n",
    "                # 第 2 个剪枝条件: 只在连续相同颜色的球的开头位置插入新球\n",
    "                if i > 0 and cur_board[i - 1] == cur_hand[j]:\n",
    "                    continue\n",
    "                \n",
    "                # 第 3 个剪枝条件: 只在以下两种情况放置新球\n",
    "                choose = False\n",
    "                #  - 第 1 种情况 : 当前球颜色与后面的球的颜色相同\n",
    "                if i < len(cur_board) and cur_board[i] == cur_hand[j]:\n",
    "                    choose = True\n",
    "                #  - 第 2 种情况 : 当前后颜色相同且与当前颜色不同时候放置球\n",
    "                if 0 < i < len(cur_board) and cur_board[i - 1] == cur_board[i] and cur_board[i - 1] != cur_hand[j]:\n",
    "                    choose = True\n",
    "\n",
    "                if choose:\n",
    "                    new_board = clean(cur_board[:i] + cur_hand[j] + cur_board[i:])\n",
    "                    new_hand = cur_hand[:j] + cur_hand[j + 1:]\n",
    "                    if not new_board:\n",
    "                        return step + 1\n",
    "                    if (new_board, new_hand) not in visited:\n",
    "                        queue.append((new_board, new_hand, step + 1))\n",
    "                        visited.add((new_board, new_hand))\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinStep(self, board: str, hand: str) -> int:\n",
    "        def clean(s):\n",
    "            # 消除桌面上需要消除的球\n",
    "            n = 1\n",
    "            while n:\n",
    "                s, n = re.subn(r\"(.)\\1{2,}\", \"\", s)\n",
    "            return s\n",
    "\n",
    "        hand = \"\".join(sorted(hand))\n",
    "\n",
    "        # 初始化用队列维护的状态队列：其中的三个元素分别为桌面球状态、手中球状态和回合数\n",
    "        queue = deque([(board, hand, 0)])\n",
    "\n",
    "        # 初始化用哈希集合维护的已访问过的状态\n",
    "        visited = {(board, hand)}\n",
    "\n",
    "        while queue:\n",
    "            cur_board, cur_hand, step = queue.popleft()\n",
    "            for i, j in product(range(len(cur_board)), range(len(cur_hand))):\n",
    "                # 第 1 个剪枝条件: 当前球的颜色和上一个球的颜色相同\n",
    "                if j > 0 and cur_hand[j] == cur_hand[j - 1]:\n",
    "                    continue\n",
    "\n",
    "                # 第 2 个剪枝条件: 只在连续相同颜色的球的开头位置插入新球\n",
    "                if i > 0 and cur_board[i - 1] == cur_hand[j]:\n",
    "                    continue\n",
    "                \n",
    "                # 第 3 个剪枝条件: 只在以下两种情况放置新球\n",
    "                choose = False\n",
    "                #  - 第 1 种情况 : 当前球颜色与后面的球的颜色相同\n",
    "                if i < len(cur_board) and cur_board[i] == cur_hand[j]:\n",
    "                    choose = True\n",
    "                #  - 第 2 种情况 : 当前后颜色相同且与当前颜色不同时候放置球\n",
    "                if 0 < i < len(cur_board) and cur_board[i - 1] == cur_board[i] and cur_board[i - 1] != cur_hand[j]:\n",
    "                    choose = True\n",
    "\n",
    "                if choose:\n",
    "                    new_board = clean(cur_board[:i] + cur_hand[j] + cur_board[i:])\n",
    "                    new_hand = cur_hand[:j] + cur_hand[j + 1:]\n",
    "                    if not new_board:\n",
    "                        return step + 1\n",
    "                    if (new_board, new_hand) not in visited:\n",
    "                        queue.append((new_board, new_hand, step + 1))\n",
    "                        visited.add((new_board, new_hand))\n",
    "\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "M = float(\"inf\")\n",
    "\n",
    "# class Solution:\n",
    "#     def remove_same_boards(self, board):\n",
    "#         def recurrent(bs):\n",
    "#             res = []\n",
    "#             patience = []\n",
    "#             for b in bs + \" \":\n",
    "#                 if patience and b == patience[-1]:\n",
    "#                     patience.append(b)\n",
    "#                 else:\n",
    "#                     if len(patience) >= 3: patience = []\n",
    "#                     res += patience\n",
    "#                     patience = [b]\n",
    "#             return \"\".join(res)\n",
    "        \n",
    "#         _b = recurrent(board)\n",
    "#         while board != _b:\n",
    "#             board = _b\n",
    "#             _b = recurrent(_b)\n",
    "        \n",
    "#         return _b\n",
    "\n",
    "#     def findMinStep(self , board: str, hand: str) -> int:\n",
    "#         my_balls = defaultdict(int)\n",
    "#         for w in hand:\n",
    "#             my_balls[w] += 1\n",
    "        \n",
    "#         def dfs(bs, mbs):\n",
    "#             # 若当前桌面为空，则说明当前方案可行，返回0\n",
    "#             if len(bs) == 0: \n",
    "#                 return 0\n",
    "#             # 若当前桌面不为空，且没有可用的球了，则说明当前方案不可行，返回-1\n",
    "#             else:\n",
    "#                 if sum(mbs.values()) == 0:\n",
    "#                     return -1\n",
    "            \n",
    "#             # 若当前桌上只有一个球，则看看手上有没有相同的两个球\n",
    "#             if len(bs) == 1:\n",
    "#                 if mbs[bs] >= 2: \n",
    "#                     return 2\n",
    "#                 # 否则说明当前情况不可行\n",
    "#                 else: return -1\n",
    "            \n",
    "#             # 记录当前需要用到的球的数量\n",
    "#             bc = M\n",
    "\n",
    "#             # 遍历桌面上的球\n",
    "#             for bi, b in enumerate(bs[:-1]):\n",
    "#                 # 每一个位置都可以插入球\n",
    "#                 # 看看手上有没有相同且足够凑成3个的球\n",
    "#                 ibn = 0\n",
    "#                 # 若当前球的下一个球和当前球一样，或当前球的上一个球和当前球一样，则插入一个即可\n",
    "#                 if bs[bi + 1] == b or (bi > 0 and bs[bi - 1] == b):\n",
    "#                     if mbs[b] >= 1:\n",
    "#                         ibn = 1\n",
    "#                 # 若不一样，则插入2个\n",
    "#                 else:\n",
    "#                     if mbs[b] >= 2:\n",
    "#                         ibn = 2\n",
    "                \n",
    "#                 # 若选不到球则跳过\n",
    "#                 if ibn == 0: continue\n",
    "\n",
    "#                 # 做出选择\n",
    "#                 mbs[b] -= ibn\n",
    "#                 c = dfs(self.remove_same_boards(f\"{bs[:bi]}{b * ibn}{bs[bi:]}\"), mbs)\n",
    "#                 # 若当前方案可行，则\n",
    "#                 if c != -1:\n",
    "#                     bc = min(bc, c + ibn)\n",
    "#                 # 撤销选择\n",
    "#                 mbs[b] += ibn\n",
    "\n",
    "#             # 若当前有解则返回解的个数\n",
    "#             if bc != M: return bc\n",
    "#             else: return -1\n",
    "        \n",
    "#         return dfs(board, my_balls)\n",
    "\n",
    "class Solution:\n",
    "    def findMinStep(self, board: str, hand: str) -> int:\n",
    "        def clean(s):\n",
    "            # 消除桌面上需要消除的球\n",
    "            n = 1\n",
    "            while n:\n",
    "                s, n = re.subn(r\"(.)\\1{2,}\", \"\", s)\n",
    "            return s\n",
    "\n",
    "        hand = \"\".join(sorted(hand))\n",
    "\n",
    "        # 初始化用队列维护的状态队列：其中的三个元素分别为桌面球状态、手中球状态和回合数\n",
    "        queue = deque([(board, hand, 0)])\n",
    "\n",
    "        # 初始化用哈希集合维护的已访问过的状态\n",
    "        visited = {(board, hand)}\n",
    "\n",
    "        while queue:\n",
    "            cur_board, cur_hand, step = queue.popleft()\n",
    "            for i, j in product(range(len(cur_board) + 1), range(len(cur_hand))):\n",
    "                # 第 1 个剪枝条件: 当前球的颜色和上一个球的颜色相同\n",
    "                if j > 0 and cur_hand[j] == cur_hand[j - 1]:\n",
    "                    continue\n",
    "\n",
    "                # 第 2 个剪枝条件: 只在连续相同颜色的球的开头位置插入新球\n",
    "                if i > 0 and cur_board[i - 1] == cur_hand[j]:\n",
    "                    continue\n",
    "                \n",
    "                # 第 3 个剪枝条件: 只在以下两种情况放置新球\n",
    "                choose = False\n",
    "                #  - 第 1 种情况 : 当前球颜色与后面的球的颜色相同\n",
    "                if i < len(cur_board) and cur_board[i] == cur_hand[j]:\n",
    "                    choose = True\n",
    "                #  - 第 2 种情况 : 当前后颜色相同且与当前颜色不同时候放置球\n",
    "                if 0 < i < len(cur_board) and cur_board[i - 1] == cur_board[i] and cur_board[i - 1] != cur_hand[j]:\n",
    "                    choose = True\n",
    "\n",
    "                if choose:\n",
    "                    new_board = clean(cur_board[:i] + cur_hand[j] + cur_board[i:])\n",
    "                    new_hand = cur_hand[:j] + cur_hand[j + 1:]\n",
    "                    if not new_board:\n",
    "                        return step + 1\n",
    "                    if (new_board, new_hand) not in visited:\n",
    "                        queue.append((new_board, new_hand, step + 1))\n",
    "                        visited.add((new_board, new_hand))\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinStep(self, board: str, hand: str) -> int:\n",
    "        visited = {(board,hand)}\n",
    "        todo = [(board,hand)]\n",
    "        \n",
    "        def eliminate(content: str):\n",
    "            x = re.search(\"R{3,}|Y{3,}|B{3,}|G{3,}|W{3,}\", content)\n",
    "            while len(content)>0 and x:\n",
    "                content = content[0:x.span()[0]] + content[x.span()[1]:]\n",
    "                x = re.search(\"R{3,}|Y{3,}|B{3,}|G{3,}|W{3,}\", content)\n",
    "            return content\n",
    "\n",
    "        # bfs\n",
    "        while todo:\n",
    "            _board, _hand = todo.pop(0)\n",
    "            for i in range(len(_hand)):\n",
    "                # 手中的相同颜色的球，仅使用一次\n",
    "                if i == _hand.index(_hand[i]):\n",
    "                    for pos in range(len(_board)+1):\n",
    "                        # 仅插相同颜色的球的左侧，\n",
    "                        if pos > 0 and _board[pos-1] == _hand[i] : continue\n",
    "                        # 左右两边球不同，不能得到更好解\n",
    "                        # if pos > 0 and pos < len(_board) and _board[pos] != _hand[i] and _board[pos-1] != _board[pos]: continue\n",
    "                        choose = False\n",
    "                        #  - 第 1 种情况 : 当前球颜色与后面的球的颜色相同\n",
    "                        if pos < len(_board) and _board[pos] == _hand[i]: \n",
    "                            choose = True\n",
    "                        if 0 < pos < len(_board) and _board[pos - 1] == _board[pos] and _board[pos - 1] != _hand[i]:\n",
    "                            choose = True                                            \n",
    "                        if choose:\n",
    "                            inserted = eliminate(_board[0:pos]+_hand[i]+_board[pos:])\n",
    "                            if inserted == \"\":\n",
    "                                return len(hand) - len(_hand) + 1\n",
    "                            if (inserted, _hand[0:i]+_hand[i+1:]) not in visited:\n",
    "                                visited.add((inserted, _hand[0:i]+_hand[i+1:]))\n",
    "                                todo.append((inserted, _hand[0:i]+_hand[i+1:]))\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "ptn = re.compile(r'(\\w)\\1{2,}')\n",
    "def make_hands(hand: str):\n",
    "    for ball in set(hand):\n",
    "        yield ball, hand.replace(ball, '', 1)\n",
    "def clean_board(board, ct):\n",
    "    while ct:\n",
    "        board, ct = ptn.subn('', board)\n",
    "    return board\n",
    "def make_boards(board, ball):\n",
    "    for t in re.finditer(r'[{}]+'.format(ball), board): #找跟球同色的位置\n",
    "        yield clean_board(board[:t.start()] + ball + board[t.start():], 1)\n",
    "    for t in re.finditer(r'([^{}])\\1+'.format(ball), board): #找已有两球同色，手里不同色球用来隔离的位置\n",
    "        yield clean_board(board[:t.start() + 1] + ball + board[t.start() + 1:], 1)\n",
    "class Solution:\n",
    "    def findMinStep(self, board: str, hand: str) -> int:\n",
    "        q, seen = deque([(board, hand, 0)]), {(board, hand)}\n",
    "        while q:\n",
    "            board, hand, t = q.popleft()\n",
    "            for ball, new_hand in make_hands(hand):\n",
    "                for new_board in make_boards(board, ball):\n",
    "                    if not new_board:\n",
    "                        return t + 1\n",
    "                    if (new_board, new_hand) not in seen:\n",
    "                        seen.add((new_board, new_hand))\n",
    "                        q.append((new_board, new_hand, t + 1))\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\r\n",
    "class Solution:\r\n",
    "    def findMinStep(self, board: str, hand: str) -> int:\r\n",
    "        def clean(board:str):\r\n",
    "            stack=[]\r\n",
    "            idx=0\r\n",
    "            L=len(board)\r\n",
    "            while idx<L:\r\n",
    "                c=board[idx]\r\n",
    "                if not stack:\r\n",
    "                    stack.append([c,1])\r\n",
    "                    idx+=1\r\n",
    "                elif c==stack[-1][0]:\r\n",
    "                    stack[-1][1]+=1\r\n",
    "                    idx+=1\r\n",
    "                else:\r\n",
    "                    if stack[-1][1]>=3:\r\n",
    "                        stack.pop()\r\n",
    "                    else:\r\n",
    "                        stack.append([c,1])\r\n",
    "                        idx+=1\r\n",
    "            if stack[-1][1]>=3:\r\n",
    "                stack.pop()\r\n",
    "            return ''.join([c*v for c,v in stack])\r\n",
    "        \r\n",
    "        # assert clean('WWBBBWW')==''\r\n",
    "        # assert clean('WWRRRBBWW')=='WWBBWW'\r\n",
    "        hand=''.join(sorted(hand))\r\n",
    "        queue=[(board,hand,0)]\r\n",
    "        visited=set()\r\n",
    "        visited.add((board,hand))\r\n",
    "        while queue:\r\n",
    "            temp=[]\r\n",
    "            while queue:\r\n",
    "                _board,_hand,step=queue.pop()\r\n",
    "                for i in range(len(_board)+1):\r\n",
    "                    for j in range(len(_hand)):\r\n",
    "                        if j>0 and _hand[j]==_hand[j-1]:\r\n",
    "                            continue\r\n",
    "                        if i>0 and _board[i-1]==_hand[j]:\r\n",
    "                            continue\r\n",
    "\r\n",
    "                        choose=i<len(_board) and _board[i]==_hand[j]\r\n",
    "                        if not choose:\r\n",
    "                            choose=0<i<len(_board) and _board[i]==_board[i-1] and _board[i]!=_hand[j]\r\n",
    "                        if choose:\r\n",
    "                            new_board=_board[:i]+_hand[j]+_board[i:]\r\n",
    "                            new_board=clean(new_board)\r\n",
    "                            if not new_board:\r\n",
    "                                return step+1\r\n",
    "                            new_hand=_hand[:j]+_hand[j+1:]\r\n",
    "                            if (new_board, new_hand) not in visited:\r\n",
    "                                temp.append((new_board,new_hand,step+1))\r\n",
    "                                visited.add((new_board,new_hand))\r\n",
    "            queue=temp\r\n",
    "        return -1\r\n",
    "\r\n",
    "                \r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# from queue import Queue\r\n",
    "from collections import deque\r\n",
    "import re\r\n",
    "class Solution:\r\n",
    "    def findMinStep(self, board: str, hand: str) -> int:\r\n",
    "        def clean(s:str):\r\n",
    "            n=1\r\n",
    "            while n:\r\n",
    "                s,n=re.subn(r'(.)\\1{2,}','',s)\r\n",
    "            return s\r\n",
    "        \r\n",
    "        hand=''.join(sorted(hand))\r\n",
    "        queue=deque()\r\n",
    "        queue.append([board,hand,0])\r\n",
    "        visited={(board,hand)}\r\n",
    "        while queue:\r\n",
    "            board,hand,step=queue.popleft()\r\n",
    "            for i in range(len(board)+1):\r\n",
    "                for j in range(len(hand)):\r\n",
    "                    if i>0 and board[i-1]==hand[j]:\r\n",
    "                        continue\r\n",
    "                    if j>0 and hand[j-1]==hand[j]:\r\n",
    "                        continue\r\n",
    "                    \r\n",
    "                    choose=i<len(board) and board[i]==hand[j]\r\n",
    "                    if not choose:\r\n",
    "                        choose=0<i<len(board) and board[i-1]==board[i] and board[i]!=hand[j]\r\n",
    "                    if choose:\r\n",
    "                        new_board=clean(board[:i]+hand[j]+board[i:])\r\n",
    "                        if not new_board:\r\n",
    "                            return step+1\r\n",
    "                        new_hand=hand[:j]+hand[j+1:]\r\n",
    "                        if (new_board,new_hand) not in visited:\r\n",
    "                            queue.append([new_board,new_hand,step+1])\r\n",
    "                            visited.add((new_board,new_hand))\r\n",
    "        return -1\r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    #mp=dict()\n",
    "    def findMinStep(self, board: str, hand: str) -> int:\n",
    "        '''def backtrace(board,hand,used):\n",
    "            if not board:return 0\n",
    "            if not used:return -1\n",
    "            if board+'_'+str(used) in Solution.mp:return Solution.mp[board+'_'+str(used)]\n",
    "            res,m=float('inf'),len(board)\n",
    "            for i in range(n):\n",
    "                if used&(i<<(n-1-i)):\n",
    "                    nxt=used-(1<<(n-1-i))\n",
    "                    for j in range(m+1):\n",
    "                        ok=False\n",
    "                        if 0<j<m and board[j]==board[j-1] and board[j-1]!=hand[i]:ok=True\n",
    "                        if j<m and board[j]==hand[i]:ok=True\n",
    "                        if not ok:continue\n",
    "                        s=''\n",
    "                        s+=(board[:j]+hand[i])\n",
    "                        if j<m:s+=board[j:]\n",
    "                        k=j\n",
    "                        while 0<=k<len(s):\n",
    "                            l,r=k-1,k+1\n",
    "                            while l>=0 and s[l]==s[k]:\n",
    "                                l-=1\n",
    "                            while r<len(s) and s[r]==s[k]:\n",
    "                                r+=1\n",
    "                            if (r-l-1)>2:\n",
    "                                s=s[:l+1]+s[r:]\n",
    "                                k=l if l>=0 else r\n",
    "                            else:\n",
    "                                break\n",
    "                        cnt=backtrace(s,hand,nxt)\n",
    "                        if cnt>=0:\n",
    "                            res=min(res,cnt+1)\n",
    "            Solution.mp[board+'_'+str(used)]=res if res<float('inf') else -1\n",
    "            return Solution.mp[board+'_'+str(used)]\n",
    "        #mp=dict()\n",
    "        n=len(hand)\n",
    "        return backtrace(board,hand,(1<<n)-1)'''\n",
    "        def backtrace(board,hand,used):\n",
    "            if not board:return 0\n",
    "            if not used:return -1\n",
    "            if board+'_'+str(used) in mp:return mp[board+'_'+str(used)]\n",
    "            res,m=float('inf'),len(board)\n",
    "            for i in range(n):\n",
    "                if used&(1<<(n-1-i)):\n",
    "                    nxt=used-(1<<(n-1-i))\n",
    "                    for j in range(m+1):\n",
    "                        ok=False\n",
    "                        if 0<j<m and board[j]==board[j-1] and board[j-1]!=hand[i]:ok=True\n",
    "                        if j<m and board[j]==hand[i]:ok=True\n",
    "                        if not ok:continue\n",
    "                        s=''\n",
    "                        s+=(board[:j]+hand[i])\n",
    "                        if j<m:s+=board[j:]\n",
    "                        k=j\n",
    "                        while 0<=k<len(s):\n",
    "                            l,r=k-1,k+1\n",
    "                            while l>=0 and s[l]==s[k]:\n",
    "                                l-=1\n",
    "                            while r<len(s) and s[r]==s[k]:\n",
    "                                r+=1\n",
    "                            if (r-l-1)>2:\n",
    "                                s=s[:l+1]+s[r:]\n",
    "                                k=l if l>=0 else r\n",
    "                            else:\n",
    "                                break\n",
    "                        cnt=backtrace(s,hand,nxt)\n",
    "                        #print(i,j,s,bin(nxt),cnt)\n",
    "                        if cnt>=0:\n",
    "                            res=min(res,cnt+1)\n",
    "            mp[board+'_'+str(used)]=res if res<float('inf') else -1\n",
    "            return mp[board+'_'+str(used)]\n",
    "        mp=dict()\n",
    "        n=len(hand)\n",
    "        return backtrace(board,hand,(1<<n)-1)\n",
    "                            \n",
    "                        \n",
    "\n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinStep(self, board: str, hand: str) -> int:\n",
    "        def backtrace(board,hand,used):\n",
    "            if not board:return 0\n",
    "            if not used:return -1\n",
    "            if board+'_'+str(used) in mp:return mp[board+'_'+str(used)]\n",
    "            res,m=float('inf'),len(board)\n",
    "            for i in range(n):\n",
    "                if used&(1<<(n-1-i)):\n",
    "                    nxt=used-(1<<(n-1-i))\n",
    "                    for j in range(m+1):\n",
    "                        ok=False\n",
    "                        if 0<j<m and board[j]==board[j-1] and board[j-1]!=hand[i]:ok=True\n",
    "                        if j<m and board[j]==hand[i]:ok=True\n",
    "                        if not ok:continue\n",
    "                        s=''\n",
    "                        s+=(board[:j]+hand[i])\n",
    "                        if j<m:s+=board[j:]\n",
    "                        k=j\n",
    "                        while 0<=k<len(s):\n",
    "                            l,r=k-1,k+1\n",
    "                            while l>=0 and s[l]==s[k]:\n",
    "                                l-=1\n",
    "                            while r<len(s) and s[r]==s[k]:\n",
    "                                r+=1\n",
    "                            if (r-l-1)>2:\n",
    "                                s=s[:l+1]+s[r:]\n",
    "                                k=l if l>=0 else r\n",
    "                            else:\n",
    "                                break\n",
    "                        cnt=backtrace(s,hand,nxt)\n",
    "                        if cnt>=0:\n",
    "                            res=min(res,cnt+1)\n",
    "            mp[board+'_'+str(used)]=res if res<float('inf') else -1\n",
    "            return mp[board+'_'+str(used)]\n",
    "        mp=dict()\n",
    "        n=len(hand)\n",
    "        return backtrace(board,hand,(1<<n)-1)\n",
    "        '''def dfs(board,hand,avaluable):\n",
    "            if not board:return 0\n",
    "            if not hand:return -1\n",
    "            res,n=float('inf'),len(board)\n",
    "            for i in range(m):\n",
    "                if avaluable&(1<<(m-1-i)):\n",
    "                    nxt=avaluable-(1<<(m-1-i))\n",
    "                    for j in range(n+1):\n",
    "                        ok=False\n",
    "                        if 0<j<n and board[j]==board[j-1] and board[j-1]!=hand[i]:ok=True\n",
    "                        if j<n and board[j]==hand[i]:ok=True\n",
    "                        if not ok:continue\n",
    "                        s=board[:j]+hand[i]\n",
    "                        s+=board[j:]\n",
    "                        k=j\n",
    "                        while 0<=k<len(s):\n",
    "                            l,r=k-1,k+1\n",
    "                            while l>=0 and s[l]==s[k]:\n",
    "                                l-=1\n",
    "                            while r<len(s) and s[r]==s[k]:\n",
    "                                r+=1\n",
    "                            if r-l-1>2:\n",
    "                                s=s[:l+1]+s[r:]\n",
    "                                k=l if l>=0 else r\n",
    "                            else:\n",
    "                                break\n",
    "                        cnt=dfs(s,hand,nxt)\n",
    "                        if cnt>=0:\n",
    "                            res=min(res,cnt+1)\n",
    "            return res if res<float('inf') else -1\n",
    "        m=len(hand)\n",
    "        return dfs(board,hand,(1<<m)-1)'''\n",
    "\n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinStep(self, board: str, hand: str) -> int:\n",
    "        def backtrace(board,hand,used):\n",
    "            if not board:return 0\n",
    "            if not used:return -1\n",
    "            if board+'_'+str(used) in mp:return mp[board+'_'+str(used)]\n",
    "            res,m=float('inf'),len(board)\n",
    "            for i in range(n):\n",
    "                if used&(1<<(n-1-i)):\n",
    "                    nxt=used-(1<<(n-1-i))\n",
    "                    for j in range(m+1):\n",
    "                        ok=False\n",
    "                        if 0<j<m and board[j]==board[j-1] and board[j-1]!=hand[i]:ok=True\n",
    "                        if j<m and board[j]==hand[i]:ok=True\n",
    "                        if not ok:continue\n",
    "                        s=''\n",
    "                        s+=(board[:j]+hand[i])\n",
    "                        if j<m:s+=board[j:]\n",
    "                        k=j\n",
    "                        while 0<=k<len(s):\n",
    "                            l,r=k-1,k+1\n",
    "                            while l>=0 and s[l]==s[k]:\n",
    "                                l-=1\n",
    "                            while r<len(s) and s[r]==s[k]:\n",
    "                                r+=1\n",
    "                            if (r-l-1)>2:\n",
    "                                s=s[:l+1]+s[r:]\n",
    "                                k=l if l>=0 else r\n",
    "                            else:\n",
    "                                break\n",
    "                        cnt=backtrace(s,hand,nxt)\n",
    "                        if cnt>=0:\n",
    "                            res=min(res,cnt+1)\n",
    "            mp[board+'_'+str(used)]=res if res<float('inf') else -1\n",
    "            return mp[board+'_'+str(used)]\n",
    "        mp=dict()\n",
    "        n=len(hand)\n",
    "        return backtrace(board,hand,(1<<n)-1)\n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinStep(self, board: str, hand: str) -> int:\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(cur_board, cur_hand):\n",
    "            res = 6\n",
    "            if not cur_board:\n",
    "                return 0\n",
    "\n",
    "            for i, j in itertools.product(range(len(cur_board)), range(len(cur_hand))):\n",
    "                if j > 0 and cur_hand[j] == cur_hand[j - 1]:\n",
    "                    continue\n",
    "                if i > 0 and cur_board[i - 1] == cur_hand[j]:\n",
    "                    continue\n",
    "                choose = False\n",
    "                if cur_hand[j] == cur_board[i]:\n",
    "                    choose = True\n",
    "                if i > 0 and cur_board[i] == cur_board[i - 1] and cur_hand[j] != cur_board[i]:\n",
    "                    choose = True\n",
    "                if choose:\n",
    "                    new_board = clean(cur_board[:i] + cur_hand[j] + cur_board[i:])\n",
    "                    new_hand = cur_hand[:j] + cur_hand[j + 1:]\n",
    "                    res = min(res, dfs(new_board, new_hand) + 1)\n",
    "            return res\n",
    "\n",
    "        def clean(s: str):\n",
    "            n = 1\n",
    "            while n:\n",
    "                s, n = re.subn(r'(.)\\1{2,}', '', s)\n",
    "            return s\n",
    "\n",
    "        ans = dfs(board, hand)\n",
    "        if ans <= 5:\n",
    "            return ans\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinStep(self, board: str, hand: str) -> int:\n",
    "        M = len(hand)+1\n",
    "        counter = Counter(hand)\n",
    "        def valid(b):\n",
    "            ret = True\n",
    "            bcnter = Counter(b)\n",
    "            for c in bcnter:\n",
    "                if bcnter[c]+(counter[c] if c in counter else 0) <3:\n",
    "                    return False \n",
    "            return True\n",
    "        if not valid(board):\n",
    "            return -1\n",
    "        def genKey():\n",
    "            ret = \"\"\n",
    "            for k in counter:\n",
    "                if counter[k]==0:\n",
    "                    continue \n",
    "                ret+=k+str(counter[k])\n",
    "            return ret \n",
    "        def insert(b,i):\n",
    "            l,r = i,i+1\n",
    "            while l>=0:\n",
    "                lc,rc = 1,0\n",
    "                while l>0 and b[l-1]==b[l]:\n",
    "                    lc+=1\n",
    "                    l-=1 \n",
    "                while r<len(b) and  b[r]==b[l]:\n",
    "                    r+=1\n",
    "                    rc+=1\n",
    "                # print(lc,rc,l,r)\n",
    "                if lc+rc<3:\n",
    "                    # print(l,r,b)\n",
    "                    return b[:l+lc]+b[r-rc:]\n",
    "                l-=1\n",
    "            # print(b,l,r,i)\n",
    "            return b[r:]\n",
    "\n",
    "\n",
    "        dp = {}\n",
    "        def dfs(b):\n",
    "            h = genKey()\n",
    "            # print(b,h)\n",
    "\n",
    "            if len(b)==0:\n",
    "                return 0 \n",
    "            if len(h)==0:\n",
    "                return M \n",
    "            if (b,h) in dp:\n",
    "                return dp[(b,h)]\n",
    "            if not valid(b):\n",
    "                return M \n",
    "\n",
    "            N = len(b)\n",
    "            ans = M\n",
    "            for k in counter:\n",
    "                if counter[k]==0:\n",
    "                    continue \n",
    "                \n",
    "                c = k \n",
    "                counter[k]-=1\n",
    "                hk = genKey()\n",
    "                i=0\n",
    "                # if b==\"BB\":\n",
    "                #     print(b,c,hk)\n",
    "                while i<N:\n",
    "                    if i-1>0 and b[i-1]==c:\n",
    "                        i+=1\n",
    "                        continue \n",
    "                    if i-1>0 and b[i-1]!=c and b[i]!=c and b[i-1]!=b[i]:\n",
    "                        i+=1\n",
    "                        continue \n",
    "                    if b[i]!=c:\n",
    "                        ans = min(dfs(b[0:i]+c+b[i:])+1,ans)\n",
    "                    else:\n",
    "                        ans = min(dfs(insert(b[0:i]+c+b[i:],i))+1,ans)\n",
    "                        # if b==\"BB\":\n",
    "                        #     print(insert(b[0:i]+c+b[i:],i),b,c,hk,ans)\n",
    "                    i+=1\n",
    "                counter[k]+=1\n",
    "            dp[(b,h)] = ans\n",
    "            return ans \n",
    "        ret = dfs(board)\n",
    "        return ret if ret<M else -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "def vanish(s: str) -> str:\n",
    "    st: list[str] = list()\n",
    "\n",
    "    def poptail() -> None:\n",
    "        i = -2\n",
    "        while i >= -len(st) and st[i] == st[-1]:\n",
    "            i -= 1\n",
    "\n",
    "        if i < -3:\n",
    "            while i < -1:\n",
    "                st.pop()\n",
    "                i += 1\n",
    "    \n",
    "    for c in s:\n",
    "        if st and c != st[-1]:\n",
    "            poptail()\n",
    "        st.append(c)\n",
    "    poptail()   \n",
    "    return ''.join(st)\n",
    "\n",
    "class Solution:\n",
    "    def findMinStep(self, board: str, hand: str) -> int:\n",
    "        bfs: deque[tuple[int, str, str]] = deque()\n",
    "        bfs.append((0, board, ''.join(sorted(hand))))\n",
    "        vis = {board}\n",
    "\n",
    "        while bfs:\n",
    "            ops, bd, hd = bfs.popleft()\n",
    "            n = len(bd)\n",
    "            m = len(hd)\n",
    "            if n == 0: return ops\n",
    "            for j in range(m):\n",
    "                # use one of same color in hand\n",
    "                if j > 0 and hd[j] == hd[j - 1]: continue\n",
    "                nxt_hd = hd[:j] + hd[j + 1:]\n",
    "                for i in range(n + 1):\n",
    "                    # check end position of continous color in board\n",
    "                    if i < n and hd[j] == bd[i]: continue\n",
    "                    # skip position that after insertion three different colors are formed\n",
    "                    if 0 < i < n and bd[i - 1] != bd[i] and bd[i - 1] != hd[j] and bd[i] != hd[j]: continue\n",
    "                    nxt_bd = vanish(bd[:i] + hd[j] + bd[i:])\n",
    "                    if nxt_bd not in vis:\n",
    "                        vis.add(nxt_bd)\n",
    "                        bfs.append((ops + 1, nxt_bd, nxt_hd))\n",
    "        \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from re import sub, findall\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def findMinStep(self, board: str, hand: str) -> int:\n",
    "        bfs: deque[tuple[int, str, str]] = deque()\n",
    "        bfs.append((0, board, ''.join(sorted(hand))))\n",
    "        vis = {board}\n",
    "\n",
    "        while bfs:\n",
    "            ops, bd, hd = bfs.popleft()\n",
    "            n = len(bd)\n",
    "            m = len(hd)\n",
    "            if n == 0: return ops\n",
    "            for j in range(m):\n",
    "                # use one of same color in hand\n",
    "                if j > 0 and hd[j] == hd[j - 1]: continue\n",
    "                nxt_hd = hd[:j] + hd[j + 1:]\n",
    "                for i in range(n + 1):\n",
    "                    # check end position of continous color in board\n",
    "                    if i < n and hd[j] == bd[i]: continue\n",
    "                    # skip position that after insertion three different colors are formed\n",
    "                    if 0 < i < n and bd[i - 1] != bd[i] and bd[i - 1] != hd[j] and bd[i] != hd[j]: continue\n",
    "                    nxt_bd = bd[:i] + hd[j] + bd[i:]\n",
    "                    while findall(\"(W{3,}|R{3,}|B{3,}|G{3,}|Y{3,})\", nxt_bd):\n",
    "                        nxt_bd = sub(\"(W{3,}|R{3,}|B{3,}|G{3,}|Y{3,})\", \"\", nxt_bd)\n",
    "                    if nxt_bd not in vis:\n",
    "                        vis.add(nxt_bd)\n",
    "                        bfs.append((ops + 1, nxt_bd, nxt_hd))\n",
    "        \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# COLORS = [\"R\", \"Y\", \"B\", \"G\", \"W\"]\n",
    "# class Solution:\n",
    "#     def findMinStep(self, board: str, hand: str) -> int:\n",
    "#         # 单纯检测一下board里有没有加上手上的还不能够3个的球，直接返回-1\n",
    "#         cnts, cnts_b = Counter(hand), Counter(board)\n",
    "#         total = len(hand)\n",
    "#         if any(cnts_b[k] + cnts[k] < 3 for k in cnts_b.keys()):\n",
    "#             return -1\n",
    "\n",
    "#         @lru_cache(None)\n",
    "#         def dfs(bd, hd):\n",
    "#             # 全部消掉了，返回所用的球数\n",
    "#             if len(bd) <= 0:\n",
    "#                 return total - sum(hd)\n",
    "#             n = len(bd)\n",
    "#             ans = inf\n",
    "#             # 遍历手上的球的颜色\n",
    "#             for i, v in enumerate(hd):\n",
    "#                 # 如果该颜色还有球可以用\n",
    "#                 if v:\n",
    "#                     cp = list(hd)\n",
    "#                     # 用掉这个球\n",
    "#                     cp[i] -= 1\n",
    "#                     nt = tuple(cp)\n",
    "#                     # 枚举插入位置\n",
    "#                     for j in range(n + 1):\n",
    "#                         ans = min(ans, dfs(in_a_row(bd[:j] + COLORS[i] + bd[j:]), nt))\n",
    "#             return ans\n",
    "        \n",
    "#         @lru_cache(None)\n",
    "#         def in_a_row(bd):\n",
    "#             l = r = 0\n",
    "#             while l < len(bd):\n",
    "#                 # 判断有没有连续三个一样的球，有的话就剪掉bd[l:r]，迭代返回\n",
    "#                 while r < len(bd) and bd[r] == bd[l]:\n",
    "#                     r += 1\n",
    "#                 if r - l > 2:\n",
    "#                     return in_a_row(bd[:l] + bd[r:])\n",
    "#                 l = r\n",
    "#             return bd\n",
    "\n",
    "#         # 手上的以不同颜色的球计数的tuple作为传参，直接避免尝试重复的球\n",
    "#         start = [cnts[c] for c in COLORS]\n",
    "#         res = dfs(board, tuple(start))\n",
    "#         return res if res != inf else -1\n",
    "COLORS = [\"R\", \"Y\", \"B\", \"G\", \"W\"]\n",
    "class Solution:\n",
    "    def findMinStep(self, board: str, hand: str) -> int:\n",
    "        # @lru_cache(None)\n",
    "        def clean(s):\n",
    "            # 消除桌面上需要消除的球\n",
    "            n = 1\n",
    "            while n:\n",
    "                s, n = re.subn(r\"(.)\\1{2,}\", \"\", s)\n",
    "            return s\n",
    "\n",
    "        cnts = Counter(hand)\n",
    "        start = [cnts[c] for c in COLORS]\n",
    "        hand = tuple(start)\n",
    "\n",
    "        # 初始化用双端队列维护的状态队列：其中的三个元素分别为当前桌面的球、当期手中的球、当前回合数\n",
    "        queue = deque([(board, hand, 0)])\n",
    "\n",
    "        # 记忆化\n",
    "        visited = {(board, hand)}\n",
    "\n",
    "        while queue:\n",
    "            cur_board, cur_hand, step = queue.popleft()\n",
    "            for i in range(len(cur_board) + 1):\n",
    "                for j in range(len(cur_hand)):\n",
    "                    if not cur_hand[j]:\n",
    "                        continue\n",
    "                    c = COLORS[j]\n",
    "                    # 第 1 个剪枝条件: 只在连续相同颜色的球的开头位置插入新球(在它前面插入过了，不需要再插入，意义相同)\n",
    "                    if i > 0 and cur_board[i - 1] == c:\n",
    "                        continue\n",
    "\n",
    "                    # 第 2 个剪枝条件: 只在以下两种情况放置新球\n",
    "                    #  - 第 1 种情况 : 当前后颜色相同且与当前颜色不同时候放置球\n",
    "                    #  - 第 2 种情况 : 当前球颜色与后面的球的颜色相同\n",
    "                    choose = False\n",
    "                    if 0 < i < len(cur_board) and cur_board[i - 1] == cur_board[i] and cur_board[i - 1] != c:\n",
    "                        choose = True\n",
    "                    if i < len(cur_board) and cur_board[i] == c:\n",
    "                        choose = True\n",
    "\n",
    "                    if choose:\n",
    "                        cp = list(cur_hand)\n",
    "                        cp[j] -= 1\n",
    "                        b2, h2 = clean(cur_board[:i] + c + cur_board[i:]), tuple(cp)\n",
    "                        if not b2:\n",
    "                            return step + 1\n",
    "                        if (b2, h2) not in visited:\n",
    "                            queue.append((b2, h2, step + 1))\n",
    "                            visited.add((b2, h2))\n",
    "                            visited.add((b2[::-1], h2))\n",
    "\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import re\n",
    "from functools import lru_cache\n",
    "from itertools import product\n",
    "\n",
    "class Solution:\n",
    "    def findMinStep(self, board: str, hand: str) -> int:\n",
    "        ans = self.dfs(board, \"\".join(sorted(hand)))\n",
    "        return ans if ans <= 5 else -1\n",
    "\n",
    "    @lru_cache(None)\n",
    "    def dfs(self, cur_board: str, cur_hand: str):\n",
    "        if not cur_board:\n",
    "            return 0\n",
    "        \n",
    "        res = 6\n",
    "        for i, j in product(range(len(cur_board) + 1), range(len(cur_hand))):\n",
    "            # 第 1 个剪枝条件: 手中颜色相同的球只需要考虑其中一个即可\n",
    "            if j > 0 and cur_hand[j] == cur_hand[j - 1]:\n",
    "                continue\n",
    "\n",
    "            # 第 2 个剪枝条件: 只在连续相同颜色的球的开头位置插入新球\n",
    "            if i > 0 and cur_board[i - 1] == cur_hand[j]:\n",
    "                continue\n",
    "\n",
    "            # 第 3 个剪枝条件: 只考虑放置新球后有可能得到更优解的位置\n",
    "            choose = False\n",
    "            #  - 第 1 种情况 : 当前球颜色与后面的球的颜色相同\n",
    "            if i < len(cur_board) and cur_board[i] == cur_hand[j]:\n",
    "                choose = True\n",
    "            #  - 第 2 种情况 : 当前后颜色相同且与当前颜色不同时候放置球\n",
    "            if 0 < i < len(cur_board) and cur_board[i - 1] == cur_board[i] and cur_board[i - 1] != cur_hand[j]:\n",
    "                choose = True\n",
    "            \n",
    "            if choose:\n",
    "                new_board = self.clean(cur_board[:i] + cur_hand[j] + cur_board[i:])\n",
    "                new_hand = cur_hand[:j] + cur_hand[j + 1:]\n",
    "                res = min(res, self.dfs(new_board, new_hand) + 1)\n",
    "        return res\n",
    "\n",
    "    @staticmethod\n",
    "    def clean(s):\n",
    "        n = 1\n",
    "        while n:\n",
    "            s, n = re.subn(r'(.)\\1{2,}', '', s)\n",
    "        return s\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import re\n",
    "from functools import lru_cache\n",
    "from itertools import product\n",
    "\n",
    "class Solution:\n",
    "    def findMinStep(self, board: str, hand: str) -> int:\n",
    "        ans = self.dfs(board, \"\".join(sorted(hand)))\n",
    "        return ans if ans <= 5 else -1\n",
    "\n",
    "    @lru_cache(None)\n",
    "    def dfs(self, cur_board: str, cur_hand: str):\n",
    "        if not cur_board:\n",
    "            return 0\n",
    "        \n",
    "        res = 6\n",
    "        for i, j in product(range(len(cur_board) + 1), range(len(cur_hand))):\n",
    "            # 第 1 个剪枝条件: 手中颜色相同的球只需要考虑其中一个即可\n",
    "            if j > 0 and cur_hand[j] == cur_hand[j - 1]:\n",
    "                continue\n",
    "\n",
    "            # 第 2 个剪枝条件: 只在连续相同颜色的球的开头位置插入新球\n",
    "            if i > 0 and cur_board[i - 1] == cur_hand[j]:\n",
    "                continue\n",
    "\n",
    "            # 第 3 个剪枝条件: 只考虑放置新球后有可能得到更优解的位置\n",
    "            choose = False\n",
    "            #  - 第 1 种情况 : 当前球颜色与后面的球的颜色相同\n",
    "            if i < len(cur_board) and cur_board[i] == cur_hand[j]:\n",
    "                choose = True\n",
    "            #  - 第 2 种情况 : 当前后颜色相同且与当前颜色不同时候放置球\n",
    "            if 0 < i < len(cur_board) and cur_board[i - 1] == cur_board[i] and cur_board[i - 1] != cur_hand[j]:\n",
    "                choose = True\n",
    "            \n",
    "            if choose:\n",
    "                new_board = self.clean(cur_board[:i] + cur_hand[j] + cur_board[i:])\n",
    "                new_hand = cur_hand[:j] + cur_hand[j + 1:]\n",
    "                res = min(res, self.dfs(new_board, new_hand) + 1)\n",
    "        return res\n",
    "\n",
    "    @staticmethod\n",
    "    def clean(s):\n",
    "        n = 1\n",
    "        while n:\n",
    "            s, n = re.subn(r'(.)\\1{2,}', '', s)\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import re\n",
    "from functools import lru_cache\n",
    "from itertools import product\n",
    "\n",
    "class Solution:\n",
    "    def findMinStep(self, board: str, hand: str) -> int:\n",
    "        ans = self.dfs(board, \"\".join(sorted(hand)))\n",
    "        return ans if ans <= 5 else -1\n",
    "\n",
    "    @lru_cache(None)\n",
    "    def dfs(self, cur_board: str, cur_hand: str):\n",
    "        if not cur_board:\n",
    "            return 0\n",
    "        \n",
    "        res = 6\n",
    "        for i, j in product(range(len(cur_board) + 1), range(len(cur_hand))):\n",
    "            # 第 1 个剪枝条件: 手中颜色相同的球只需要考虑其中一个即可\n",
    "            if j > 0 and cur_hand[j] == cur_hand[j - 1]:\n",
    "                continue\n",
    "\n",
    "            # 第 2 个剪枝条件: 只在连续相同颜色的球的开头位置插入新球\n",
    "            if i > 0 and cur_board[i - 1] == cur_hand[j]:\n",
    "                continue\n",
    "\n",
    "            # 第 3 个剪枝条件: 只考虑放置新球后有可能得到更优解的位置\n",
    "            choose = False\n",
    "            #  - 第 1 种情况 : 当前球颜色与后面的球的颜色相同\n",
    "            if i < len(cur_board) and cur_board[i] == cur_hand[j]:\n",
    "                choose = True\n",
    "            #  - 第 2 种情况 : 当前后颜色相同且与当前颜色不同时候放置球\n",
    "            if 0 < i < len(cur_board) and cur_board[i - 1] == cur_board[i] and cur_board[i - 1] != cur_hand[j]:\n",
    "                choose = True\n",
    "            \n",
    "            if choose:\n",
    "                new_board = self.clean(cur_board[:i] + cur_hand[j] + cur_board[i:])\n",
    "                new_hand = cur_hand[:j] + cur_hand[j + 1:]\n",
    "                res = min(res, self.dfs(new_board, new_hand) + 1)\n",
    "        return res\n",
    "\n",
    "    @staticmethod\n",
    "    def clean(s):\n",
    "        n = 1\n",
    "        while n:\n",
    "            s, n = re.subn(r'(.)\\1{2,}', '', s)\n",
    "        return s\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    @lru_cache(None)\n",
    "    def dfs(self, board, hand):\n",
    "        if board == \"\":\n",
    "            return 0\n",
    "\n",
    "        res = 6\n",
    "        used = set()\n",
    "        for i in range(len(hand)):\n",
    "            if hand[i] in used:\n",
    "                continue\n",
    "            used.add(hand[i])\n",
    "            for j in range(len(board)):\n",
    "                if j > 0 and board[j-1] == hand[i]:\n",
    "                    continue\n",
    "                if board[j] == hand[i] or (j > 0 and board[j-1] == board[j] and board[j-1] != hand[i]):\n",
    "                    new_board = board[:j] + hand[i] + board[j:]\n",
    "                    new_board = self.clean_triple(new_board)\n",
    "                    res = min(self.dfs(new_board, hand[:i] + hand[i + 1:]) + 1, res)\n",
    "        return res\n",
    "\n",
    "    def clean_triple(self, board):\n",
    "        for i in range(len(board) - 2):\n",
    "            if board[i] == board[i + 1] and board[i + 1] == board[i + 2]:\n",
    "                end = i + 2\n",
    "                while True:\n",
    "                    if end + 1 < len(board) and board[end+1] == board[i]:\n",
    "                        end += 1\n",
    "                    else:\n",
    "                        break\n",
    "                board = self.clean_triple(board[:i] + board[end + 1:])\n",
    "                return board\n",
    "        return board\n",
    "\n",
    "    def findMinStep(self, board, hand):\n",
    "        ans = self.dfs(board, hand)\n",
    "        return ans if ans <= 5 else -1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import re\n",
    "from functools import lru_cache\n",
    "from itertools import product\n",
    "\n",
    "class Solution:\n",
    "    def findMinStep(self, board: str, hand: str) -> int:\n",
    "        ans = self.dfs(board, \"\".join(sorted(hand)))\n",
    "        return ans if ans <= 5 else -1\n",
    "\n",
    "    @lru_cache(None)\n",
    "    def dfs(self, cur_board: str, cur_hand: str):\n",
    "        if not cur_board:\n",
    "            return 0\n",
    "        \n",
    "        res = 6\n",
    "        for i, j in product(range(len(cur_board) + 1), range(len(cur_hand))):\n",
    "            # 第 1 个剪枝条件: 手中颜色相同的球只需要考虑其中一个即可\n",
    "            if j > 0 and cur_hand[j] == cur_hand[j - 1]:\n",
    "                continue\n",
    "\n",
    "            # 第 2 个剪枝条件: 只在连续相同颜色的球的开头位置插入新球\n",
    "            if i > 0 and cur_board[i - 1] == cur_hand[j]:\n",
    "                continue\n",
    "\n",
    "            # 第 3 个剪枝条件: 只考虑放置新球后有可能得到更优解的位置\n",
    "            choose = False\n",
    "            #  - 第 1 种情况 : 当前球颜色与后面的球的颜色相同\n",
    "            if i < len(cur_board) and cur_board[i] == cur_hand[j]:\n",
    "                choose = True\n",
    "            #  - 第 2 种情况 : 当前后颜色相同且与当前颜色不同时候放置球\n",
    "            if 0 < i < len(cur_board) and cur_board[i - 1] == cur_board[i] and cur_board[i - 1] != cur_hand[j]:\n",
    "                choose = True\n",
    "            \n",
    "            if choose:\n",
    "                new_board = self.clean(cur_board[:i] + cur_hand[j] + cur_board[i:])\n",
    "                new_hand = cur_hand[:j] + cur_hand[j + 1:]\n",
    "                res = min(res, self.dfs(new_board, new_hand) + 1)\n",
    "        return res\n",
    "\n",
    "    @staticmethod\n",
    "    def clean(s):\n",
    "        n = 1\n",
    "        while n:\n",
    "            s, n = re.subn(r'(.)\\1{2,}', '', s)\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    @lru_cache(None)\n",
    "    def dfs(self, board, hand):\n",
    "        if board == \"\":\n",
    "            return 0\n",
    "\n",
    "        res = 6\n",
    "        used = set()\n",
    "        for i in range(len(hand)):\n",
    "            if hand[i] in used:\n",
    "                continue\n",
    "            used.add(hand[i])\n",
    "            for j in range(len(board)):\n",
    "                if j > 0 and board[j-1] == hand[i]:\n",
    "                    continue\n",
    "                if board[j] == hand[i] or (j > 0 and board[j-1] == board[j] and board[j-1] != hand[i]):\n",
    "                    new_board = board[:j] + hand[i] + board[j:]\n",
    "                    new_board = self.clean_triple(new_board)\n",
    "                    if new_board == \"\":\n",
    "                        return 1\n",
    "                    res = min(self.dfs(new_board, hand[:i] + hand[i + 1:]) + 1, res)\n",
    "        return res\n",
    "\n",
    "    def clean_triple(self, board):\n",
    "        for i in range(len(board) - 2):\n",
    "            if board[i] == board[i + 1] and board[i + 1] == board[i + 2]:\n",
    "                end = i + 2\n",
    "                while True:\n",
    "                    if end + 1 < len(board) and board[end+1] == board[i]:\n",
    "                        end += 1\n",
    "                    else:\n",
    "                        break\n",
    "                board = self.clean_triple(board[:i] + board[end + 1:])\n",
    "                return board\n",
    "        return board\n",
    "\n",
    "    def findMinStep(self, board, hand):\n",
    "        ans = self.dfs(board, hand)\n",
    "        return ans if ans <= 5 else -1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import re\n",
    "from functools import lru_cache\n",
    "from itertools import product\n",
    "\n",
    "class Solution:\n",
    "    def findMinStep(self, board: str, hand: str) -> int:\n",
    "        ans = self.dfs(board, \"\".join(sorted(hand)))\n",
    "        return ans if ans <= 5 else -1\n",
    "\n",
    "    @lru_cache(None)\n",
    "    def dfs(self, cur_board: str, cur_hand: str):\n",
    "        if not cur_board:\n",
    "            return 0\n",
    "        \n",
    "        res = 6\n",
    "        for i, j in product(range(len(cur_board) + 1), range(len(cur_hand))):\n",
    "            # 第 1 个剪枝条件: 手中颜色相同的球只需要考虑其中一个即可\n",
    "            if j > 0 and cur_hand[j] == cur_hand[j - 1]:\n",
    "                continue\n",
    "\n",
    "            # 第 2 个剪枝条件: 只在连续相同颜色的球的开头位置插入新球\n",
    "            if i > 0 and cur_board[i - 1] == cur_hand[j]:\n",
    "                continue\n",
    "\n",
    "            # 第 3 个剪枝条件: 只考虑放置新球后有可能得到更优解的位置\n",
    "            choose = False\n",
    "            #  - 第 1 种情况 : 当前球颜色与后面的球的颜色相同\n",
    "            if i < len(cur_board) and cur_board[i] == cur_hand[j]:\n",
    "                choose = True\n",
    "            #  - 第 2 种情况 : 当前后颜色相同且与当前颜色不同时候放置球\n",
    "            if 0 < i < len(cur_board) and cur_board[i - 1] == cur_board[i] and cur_board[i - 1] != cur_hand[j]:\n",
    "                choose = True\n",
    "            \n",
    "            if choose:\n",
    "                new_board = self.clean(cur_board[:i] + cur_hand[j] + cur_board[i:])\n",
    "                new_hand = cur_hand[:j] + cur_hand[j + 1:]\n",
    "                res = min(res, self.dfs(new_board, new_hand) + 1)\n",
    "        return res\n",
    "\n",
    "    @staticmethod\n",
    "    def clean(s):\n",
    "        n = 1\n",
    "        while n:\n",
    "            s, n = re.subn(r'(.)\\1{2,}', '', s)\n",
    "        return s\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinStep(self, board: str, hand: str) -> int:\n",
    "        def clean(s):\n",
    "            # 消除桌面上需要消除的球\n",
    "            n = 1\n",
    "            while n:\n",
    "                s, n = re.subn(r\"(.)\\1{2,}\", \"\", s)\n",
    "            return s\n",
    "\n",
    "        m = collections.defaultdict(lambda: 6)\n",
    "        cnts = collections.Counter(hand)\n",
    "\n",
    "        def back_track(s, step):\n",
    "            for i in range(len(s) + 1):\n",
    "                for c in cnts:\n",
    "                    if cnts[c] > 0:\n",
    "                        if i > 0 and s[i - 1] == c:\n",
    "                            continue\n",
    "                        if i > 0 and i < len(s) and s[i - 1] != s[i] != c:\n",
    "                            continue\n",
    "                        cnts[c] -= 1\n",
    "                        tmp = clean(s[:i] + c + s[i:])\n",
    "                        if m[tmp] > step + 1:\n",
    "                            m[tmp] = step + 1\n",
    "                            if m[tmp] + 1 < m['']:\n",
    "                                back_track(tmp, step + 1)\n",
    "                        cnts[c] += 1\n",
    "        back_track(board, 0)\n",
    "        return m[''] if m[''] < 6 else -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "COLORS = [\"R\", \"Y\", \"B\", \"G\", \"W\"]\n",
    "class Solution:\n",
    "    def findMinStep(self, board: str, hand: str) -> int:\n",
    "        @lru_cache(None)\n",
    "        def clean(s):\n",
    "            # 消除桌面上需要消除的球\n",
    "            n = 1\n",
    "            while n:\n",
    "                s, n = re.subn(r\"(.)\\1{2,}\", \"\", s)\n",
    "            return s\n",
    "\n",
    "        cnts = Counter(hand)\n",
    "        start = [cnts[c] for c in COLORS]\n",
    "        hand = tuple(start)\n",
    "\n",
    "        # 初始化用双端队列维护的状态队列：其中的三个元素分别为当前桌面的球、当期手中的球、当前回合数\n",
    "        queue = deque([(board, hand, 0)])\n",
    "\n",
    "        # 记忆化\n",
    "        visited = {(board, hand)}\n",
    "\n",
    "        while queue:\n",
    "            cur_board, cur_hand, step = queue.popleft()\n",
    "            for i in range(len(cur_board) + 1):\n",
    "                for j in range(len(cur_hand)):\n",
    "                    if not cur_hand[j]:\n",
    "                        continue\n",
    "                    c = COLORS[j]\n",
    "                    # 第 1 个剪枝条件: 只在连续相同颜色的球的开头位置插入新球(在它前面插入过了，不需要再插入，意义相同)\n",
    "                    if i > 0 and cur_board[i - 1] == c:\n",
    "                        continue\n",
    "\n",
    "                    # 第 2 个剪枝条件: 只在以下两种情况放置新球\n",
    "                    #  - 第 1 种情况 : 当前后颜色相同且与当前颜色不同时候放置球\n",
    "                    #  - 第 2 种情况 : 当前球颜色与后面的球的颜色相同\n",
    "                    choose = False\n",
    "                    if 0 < i < len(cur_board) and cur_board[i - 1] == cur_board[i] and cur_board[i - 1] != c:\n",
    "                        choose = True\n",
    "                    if i < len(cur_board) and cur_board[i] == c:\n",
    "                        choose = True\n",
    "\n",
    "                    if choose:\n",
    "                        cp = list(cur_hand)\n",
    "                        cp[j] -= 1\n",
    "                        b2, h2 = clean(cur_board[:i] + c + cur_board[i:]), tuple(cp)\n",
    "                        if not b2:\n",
    "                            return step + 1\n",
    "                        if (b2, h2) not in visited:\n",
    "                            queue.append((b2, h2, step + 1))\n",
    "                            visited.add((b2, h2))\n",
    "                            visited.add((b2[::-1], h2))\n",
    "\n",
    "        return -1\n",
    "\n",
    "# 作者：Benhao\n",
    "# 链接：https://leetcode.cn/problems/zuma-game/solutions/1091788/python-chun-bao-li-dfswei-you-hua-by-him-uk9z/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "COLORS = [\"R\", \"Y\", \"B\", \"G\", \"W\"]\n",
    "class Solution:\n",
    "    def findMinStep(self, board: str, hand: str) -> int:\n",
    "        @lru_cache(None)\n",
    "        def clean(s):\n",
    "            n = 1\n",
    "            while n:\n",
    "                s, n = re.subn(r\"(.)\\1{2,}\", \"\", s)\n",
    "            return s\n",
    "        cnts = Counter(hand)\n",
    "        start = [cnts[c] for c in COLORS]\n",
    "        hand = tuple(start)\n",
    "        queue = deque([(board, hand, 0)])\n",
    "        visited = {(board, hand)}\n",
    "        while queue:\n",
    "            cur_board, cur_hand, step = queue.popleft()\n",
    "            for i in range(len(cur_board) + 1):\n",
    "                for j in range(len(cur_hand)):\n",
    "                    if not cur_hand[j]:\n",
    "                        continue\n",
    "                    c = COLORS[j]\n",
    "                    if i > 0 and cur_board[i - 1] == c:\n",
    "                        continue\n",
    "                    choose = False\n",
    "                    if 0 < i < len(cur_board) and cur_board[i - 1] == cur_board[i] and cur_board[i - 1] != c:\n",
    "                        choose = True\n",
    "                    if i < len(cur_board) and cur_board[i] == c:\n",
    "                        choose = True\n",
    "\n",
    "                    if choose:\n",
    "                        cp = list(cur_hand)\n",
    "                        cp[j] -= 1\n",
    "                        b2, h2 = clean(cur_board[:i] + c + cur_board[i:]), tuple(cp)\n",
    "                        if not b2:\n",
    "                            return step + 1\n",
    "                        if (b2, h2) not in visited:\n",
    "                            queue.append((b2, h2, step + 1))\n",
    "                            visited.add((b2, h2))\n",
    "                            visited.add((b2[::-1], h2))\n",
    "\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "COLORS = [\"R\", \"Y\", \"B\", \"G\", \"W\"]\n",
    "class Solution:\n",
    "    def findMinStep(self, board: str, hand: str) -> int:\n",
    "        @lru_cache(None)\n",
    "        def clean(s):\n",
    "            # 消除桌面上需要消除的球\n",
    "            n = 1\n",
    "            while n:\n",
    "                s, n = re.subn(r\"(.)\\1{2,}\", \"\", s)\n",
    "            return s\n",
    "\n",
    "        cnts = Counter(hand)\n",
    "        start = [cnts[c] for c in COLORS]\n",
    "        hand = tuple(start)\n",
    "\n",
    "        # 初始化用双端队列维护的状态队列：其中的三个元素分别为当前桌面的球、当期手中的球、当前回合数\n",
    "        queue = deque([(board, hand, 0)])\n",
    "\n",
    "        # 记忆化\n",
    "        visited = {(board, hand)}\n",
    "\n",
    "        while queue:\n",
    "            cur_board, cur_hand, step = queue.popleft()\n",
    "            for i in range(len(cur_board) + 1):\n",
    "                for j in range(len(cur_hand)):\n",
    "                    if not cur_hand[j]:\n",
    "                        continue\n",
    "                    c = COLORS[j]\n",
    "                    # 第 1 个剪枝条件: 只在连续相同颜色的球的开头位置插入新球(在它前面插入过了，不需要再插入，意义相同)\n",
    "                    if i > 0 and cur_board[i - 1] == c:\n",
    "                        continue\n",
    "\n",
    "                    # 第 2 个剪枝条件: 只在以下两种情况放置新球\n",
    "                    #  - 第 1 种情况 : 当前后颜色相同且与当前颜色不同时候放置球\n",
    "                    #  - 第 2 种情况 : 当前球颜色与后面的球的颜色相同\n",
    "                    choose = False\n",
    "                    if 0 < i < len(cur_board) and cur_board[i - 1] == cur_board[i] and cur_board[i - 1] != c:\n",
    "                        choose = True\n",
    "                    if i < len(cur_board) and cur_board[i] == c:\n",
    "                        choose = True\n",
    "\n",
    "                    if choose:\n",
    "                        cp = list(cur_hand)\n",
    "                        cp[j] -= 1\n",
    "                        b2, h2 = clean(cur_board[:i] + c + cur_board[i:]), tuple(cp)\n",
    "                        if not b2:\n",
    "                            return step + 1\n",
    "                        if (b2, h2) not in visited:\n",
    "                            queue.append((b2, h2, step + 1))\n",
    "                            visited.add((b2, h2))\n",
    "                            visited.add((b2[::-1], h2))\n",
    "\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "COLORS = [\"R\", \"Y\", \"B\", \"G\", \"W\"]\n",
    "class Solution:\n",
    "    def findMinStep(self, board: str, hand: str) -> int:\n",
    "        @lru_cache(None)\n",
    "        def clean(s):\n",
    "            # 消除桌面上需要消除的球\n",
    "            n = 1\n",
    "            while n:\n",
    "                s, n = re.subn(r\"(.)\\1{2,}\", \"\", s)\n",
    "            return s\n",
    "\n",
    "        cnts = Counter(hand)\n",
    "        start = [cnts[c] for c in COLORS]\n",
    "        hand = tuple(start)\n",
    "\n",
    "        # 初始化用双端队列维护的状态队列：其中的三个元素分别为当前桌面的球、当期手中的球、当前回合数\n",
    "        queue = deque([(board, hand, 0)])\n",
    "\n",
    "        # 记忆化\n",
    "        visited = {(board, hand)}\n",
    "\n",
    "        while queue:\n",
    "            cur_board, cur_hand, step = queue.popleft()\n",
    "            for i in range(len(cur_board) + 1):\n",
    "                for j in range(len(cur_hand)):\n",
    "                    if not cur_hand[j]:\n",
    "                        continue\n",
    "                    c = COLORS[j]\n",
    "                    # 第 1 个剪枝条件: 只在连续相同颜色的球的开头位置插入新球(在它前面插入过了，不需要再插入，意义相同)\n",
    "                    if i > 0 and cur_board[i - 1] == c:\n",
    "                        continue\n",
    "\n",
    "                    # 第 2 个剪枝条件: 只在以下两种情况放置新球\n",
    "                    #  - 第 1 种情况 : 当前后颜色相同且与当前颜色不同时候放置球\n",
    "                    #  - 第 2 种情况 : 当前球颜色与后面的球的颜色相同\n",
    "                    choose = False\n",
    "                    if 0 < i < len(cur_board) and cur_board[i - 1] == cur_board[i] and cur_board[i - 1] != c:\n",
    "                        choose = True\n",
    "                    if i < len(cur_board) and cur_board[i] == c:\n",
    "                        choose = True\n",
    "\n",
    "                    if choose:\n",
    "                        cp = list(cur_hand)\n",
    "                        cp[j] -= 1\n",
    "                        b2, h2 = clean(cur_board[:i] + c + cur_board[i:]), tuple(cp)\n",
    "                        if not b2:\n",
    "                            return step + 1\n",
    "                        if (b2, h2) not in visited:\n",
    "                            queue.append((b2, h2, step + 1))\n",
    "                            visited.add((b2, h2))\n",
    "                            visited.add((b2[::-1], h2))\n",
    "\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "COLORS = [\"R\", \"Y\", \"B\", \"G\", \"W\"]\n",
    "class Solution:\n",
    "    def findMinStep(self, board: str, hand: str) -> int:\n",
    "        @lru_cache(None)\n",
    "        def clean(s):\n",
    "            # 消除桌面上需要消除的球\n",
    "            n = 1\n",
    "            while n:\n",
    "                s, n = re.subn(r\"(.)\\1{2,}\", \"\", s)\n",
    "            return s\n",
    "\n",
    "        cnts = Counter(hand)\n",
    "        start = [cnts[c] for c in COLORS]\n",
    "        hand = tuple(start)\n",
    "\n",
    "        # 初始化用双端队列维护的状态队列：其中的三个元素分别为当前桌面的球、当期手中的球、当前回合数\n",
    "        queue = deque([(board, hand, 0)])\n",
    "\n",
    "        # 记忆化\n",
    "        visited = {(board, hand)}\n",
    "\n",
    "        while queue:\n",
    "            cur_board, cur_hand, step = queue.popleft()\n",
    "            for i in range(len(cur_board) + 1):\n",
    "                for j in range(len(cur_hand)):\n",
    "                    if not cur_hand[j]:\n",
    "                        continue\n",
    "                    c = COLORS[j]\n",
    "                    # 第 1 个剪枝条件: 只在连续相同颜色的球的开头位置插入新球(在它前面插入过了，不需要再插入，意义相同)\n",
    "                    if i > 0 and cur_board[i - 1] == c:\n",
    "                        continue\n",
    "\n",
    "                    # 第 2 个剪枝条件: 只在以下两种情况放置新球\n",
    "                    #  - 第 1 种情况 : 当前后颜色相同且与当前颜色不同时候放置球\n",
    "                    #  - 第 2 种情况 : 当前球颜色与后面的球的颜色相同\n",
    "                    choose = False\n",
    "                    if 0 < i < len(cur_board) and cur_board[i - 1] == cur_board[i] and cur_board[i - 1] != c:\n",
    "                        choose = True\n",
    "                    if i < len(cur_board) and cur_board[i] == c:\n",
    "                        choose = True\n",
    "\n",
    "                    if choose:\n",
    "                        cp = list(cur_hand)\n",
    "                        cp[j] -= 1\n",
    "                        b2, h2 = clean(cur_board[:i] + c + cur_board[i:]), tuple(cp)\n",
    "                        if not b2:\n",
    "                            return step + 1\n",
    "                        if (b2, h2) not in visited:\n",
    "                            queue.append((b2, h2, step + 1))\n",
    "                            visited.add((b2, h2))\n",
    "                            visited.add((b2[::-1], h2))\n",
    "\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "COLORS = [\"R\", \"Y\", \"B\", \"G\", \"W\"]\n",
    "class Solution:\n",
    "    def findMinStep(self, board: str, hand: str) -> int:\n",
    "        @lru_cache(None)\n",
    "        def clean(s):\n",
    "            # 消除桌面上需要消除的球\n",
    "            n = 1\n",
    "            while n:\n",
    "                s, n = re.subn(r\"(.)\\1{2,}\", \"\", s)\n",
    "            return s\n",
    "\n",
    "        cnts = Counter(hand)\n",
    "        start = [cnts[c] for c in COLORS]\n",
    "        hand = tuple(start)\n",
    "\n",
    "        # 初始化用双端队列维护的状态队列：其中的三个元素分别为当前桌面的球、当期手中的球、当前回合数\n",
    "        queue = deque([(board, hand, 0)])\n",
    "\n",
    "        # 记忆化\n",
    "        visited = {(board, hand)}\n",
    "\n",
    "        while queue:\n",
    "            cur_board, cur_hand, step = queue.popleft()\n",
    "            for i in range(len(cur_board) + 1):\n",
    "                for j in range(len(cur_hand)):\n",
    "                    if not cur_hand[j]:\n",
    "                        continue\n",
    "                    c = COLORS[j]\n",
    "                    # 第 1 个剪枝条件: 只在连续相同颜色的球的开头位置插入新球(在它前面插入过了，不需要再插入，意义相同)\n",
    "                    if i > 0 and cur_board[i - 1] == c:\n",
    "                        continue\n",
    "\n",
    "                    # 第 2 个剪枝条件: 只在以下两种情况放置新球\n",
    "                    #  - 第 1 种情况 : 当前后颜色相同且与当前颜色不同时候放置球\n",
    "                    #  - 第 2 种情况 : 当前球颜色与后面的球的颜色相同\n",
    "                    choose = False\n",
    "                    if 0 < i < len(cur_board) and cur_board[i - 1] == cur_board[i] and cur_board[i - 1] != c:\n",
    "                        choose = True\n",
    "                    if i < len(cur_board) and cur_board[i] == c:\n",
    "                        choose = True\n",
    "\n",
    "                    if choose:\n",
    "                        cp = list(cur_hand)\n",
    "                        cp[j] -= 1\n",
    "                        b2, h2 = clean(cur_board[:i] + c + cur_board[i:]), tuple(cp)\n",
    "                        if not b2:\n",
    "                            return step + 1\n",
    "                        if (b2, h2) not in visited:\n",
    "                            queue.append((b2, h2, step + 1))\n",
    "                            visited.add((b2, h2))\n",
    "                            visited.add((b2[::-1], h2))\n",
    "\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "COLORS = [\"R\", \"Y\", \"B\", \"G\", \"W\"]\n",
    "class Solution:\n",
    "    def findMinStep(self, board: str, hand: str) -> int:\n",
    "        @lru_cache(None)\n",
    "        def clean(s):\n",
    "            # 消除桌面上需要消除的球\n",
    "            n = 1\n",
    "            while n:\n",
    "                s, n = re.subn(r\"(.)\\1{2,}\", \"\", s)\n",
    "            return s\n",
    "\n",
    "        cnts = Counter(hand)\n",
    "        start = [cnts[c] for c in COLORS]\n",
    "        hand = tuple(start)\n",
    "\n",
    "        # 初始化用双端队列维护的状态队列：其中的三个元素分别为当前桌面的球、当期手中的球、当前回合数\n",
    "        queue = deque([(board, hand, 0)])\n",
    "\n",
    "        # 记忆化\n",
    "        visited = {(board, hand)}\n",
    "\n",
    "        while queue:\n",
    "            cur_board, cur_hand, step = queue.popleft()\n",
    "            for i in range(len(cur_board) + 1):\n",
    "                for j in range(len(cur_hand)):\n",
    "                    if not cur_hand[j]:\n",
    "                        continue\n",
    "                    c = COLORS[j]\n",
    "                    # 第 1 个剪枝条件: 只在连续相同颜色的球的开头位置插入新球(在它前面插入过了，不需要再插入，意义相同)\n",
    "                    if i > 0 and cur_board[i - 1] == c:\n",
    "                        continue\n",
    "\n",
    "                    # 第 2 个剪枝条件: 只在以下两种情况放置新球\n",
    "                    #  - 第 1 种情况 : 当前后颜色相同且与当前颜色不同时候放置球\n",
    "                    #  - 第 2 种情况 : 当前球颜色与后面的球的颜色相同\n",
    "                    choose = False\n",
    "                    if 0 < i < len(cur_board) and cur_board[i - 1] == cur_board[i] and cur_board[i - 1] != c:\n",
    "                        choose = True\n",
    "                    if i < len(cur_board) and cur_board[i] == c:\n",
    "                        choose = True\n",
    "\n",
    "                    if choose:\n",
    "                        cp = list(cur_hand)\n",
    "                        cp[j] -= 1\n",
    "                        b2, h2 = clean(cur_board[:i] + c + cur_board[i:]), tuple(cp)\n",
    "                        if not b2:\n",
    "                            return step + 1\n",
    "                        if (b2, h2) not in visited:\n",
    "                            queue.append((b2, h2, step + 1))\n",
    "                            visited.add((b2, h2))\n",
    "                            visited.add((b2[::-1], h2))\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# COLORS = [\"R\", \"Y\", \"B\", \"G\", \"W\"]\n",
    "# class Solution:\n",
    "#     def findMinStep(self, board: str, hand: str) -> int:\n",
    "#         # 单纯检测一下board里有没有加上手上的还不能够3个的球，直接返回-1\n",
    "#         cnts, cnts_b = Counter(hand), Counter(board)\n",
    "#         total = len(hand)\n",
    "#         if any(cnts_b[k] + cnts[k] < 3 for k in cnts_b.keys()):\n",
    "#             return -1\n",
    "\n",
    "#         @lru_cache(None)\n",
    "#         def dfs(bd, hd):\n",
    "#             # 全部消掉了，返回所用的球数\n",
    "#             if len(bd) <= 0:\n",
    "#                 return total - sum(hd)\n",
    "#             n = len(bd)\n",
    "#             ans = inf\n",
    "#             # 遍历手上的球的颜色\n",
    "#             for i, v in enumerate(hd):\n",
    "#                 # 如果该颜色还有球可以用\n",
    "#                 if v:\n",
    "#                     cp = list(hd)\n",
    "#                     # 用掉这个球\n",
    "#                     cp[i] -= 1\n",
    "#                     nt = tuple(cp)\n",
    "#                     # 枚举插入位置\n",
    "#                     for j in range(n + 1):\n",
    "#                         ans = min(ans, dfs(in_a_row(bd[:j] + COLORS[i] + bd[j:]), nt))\n",
    "#             return ans\n",
    "        \n",
    "#         @lru_cache(None)\n",
    "#         def in_a_row(bd):\n",
    "#             l = r = 0\n",
    "#             while l < len(bd):\n",
    "#                 # 判断有没有连续三个一样的球，有的话就剪掉bd[l:r]，迭代返回\n",
    "#                 while r < len(bd) and bd[r] == bd[l]:\n",
    "#                     r += 1\n",
    "#                 if r - l > 2:\n",
    "#                     return in_a_row(bd[:l] + bd[r:])\n",
    "#                 l = r\n",
    "#             return bd\n",
    "\n",
    "#         # 手上的以不同颜色的球计数的tuple作为传参，直接避免尝试重复的球\n",
    "#         start = [cnts[c] for c in COLORS]\n",
    "#         res = dfs(board, tuple(start))\n",
    "#         return res if res != inf else -1\n",
    "COLORS = [\"R\", \"Y\", \"B\", \"G\", \"W\"]\n",
    "class Solution:\n",
    "    def findMinStep(self, board: str, hand: str) -> int:\n",
    "        @lru_cache(None)\n",
    "        def clean(s):\n",
    "            # 消除桌面上需要消除的球\n",
    "            n = 1\n",
    "            while n:\n",
    "                s, n = re.subn(r\"(.)\\1{2,}\", \"\", s)\n",
    "            return s\n",
    "\n",
    "        cnts = Counter(hand)\n",
    "        start = [cnts[c] for c in COLORS]\n",
    "        hand = tuple(start)\n",
    "\n",
    "        # 初始化用双端队列维护的状态队列：其中的三个元素分别为当前桌面的球、当期手中的球、当前回合数\n",
    "        queue = deque([(board, hand, 0)])\n",
    "\n",
    "        # 记忆化\n",
    "        visited = {(board, hand)}\n",
    "\n",
    "        while queue:\n",
    "            cur_board, cur_hand, step = queue.popleft()\n",
    "            for i in range(len(cur_board) + 1):\n",
    "                for j in range(len(cur_hand)):\n",
    "                    if not cur_hand[j]:\n",
    "                        continue\n",
    "                    c = COLORS[j]\n",
    "                    # 第 1 个剪枝条件: 只在连续相同颜色的球的开头位置插入新球(在它前面插入过了，不需要再插入，意义相同)\n",
    "                    if i > 0 and cur_board[i - 1] == c:\n",
    "                        continue\n",
    "\n",
    "                    # 第 2 个剪枝条件: 只在以下两种情况放置新球\n",
    "                    #  - 第 1 种情况 : 当前后颜色相同且与当前颜色不同时候放置球\n",
    "                    #  - 第 2 种情况 : 当前球颜色与后面的球的颜色相同\n",
    "                    choose = False\n",
    "                    if 0 < i < len(cur_board) and cur_board[i - 1] == cur_board[i] and cur_board[i - 1] != c:\n",
    "                        choose = True\n",
    "                    if i < len(cur_board) and cur_board[i] == c:\n",
    "                        choose = True\n",
    "\n",
    "                    if choose:\n",
    "                        cp = list(cur_hand)\n",
    "                        cp[j] -= 1\n",
    "                        b2, h2 = clean(cur_board[:i] + c + cur_board[i:]), tuple(cp)\n",
    "                        if not b2:\n",
    "                            return step + 1\n",
    "                        if (b2, h2) not in visited:\n",
    "                            queue.append((b2, h2, step + 1))\n",
    "                            visited.add((b2, h2))\n",
    "                            visited.add((b2[::-1], h2))\n",
    "\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "COLORS = [\"R\", \"Y\", \"B\", \"G\", \"W\"]\n",
    "class Solution:\n",
    "    def findMinStep(self, board: str, hand: str) -> int:\n",
    "        @lru_cache(None)\n",
    "        def clean(s):\n",
    "            # 消除桌面上需要消除的球\n",
    "            n = 1\n",
    "            while n:\n",
    "                s, n = re.subn(r\"(.)\\1{2,}\", \"\", s)\n",
    "            return s\n",
    "\n",
    "        cnts = Counter(hand)\n",
    "        start = [cnts[c] for c in COLORS]\n",
    "        hand = tuple(start)\n",
    "\n",
    "        # 初始化用双端队列维护的状态队列：其中的三个元素分别为当前桌面的球、当期手中的球、当前回合数\n",
    "        queue = deque([(board, hand, 0)])\n",
    "\n",
    "        # 记忆化\n",
    "        visited = {(board, hand)}\n",
    "\n",
    "        while queue:\n",
    "            cur_board, cur_hand, step = queue.popleft()\n",
    "            for i in range(len(cur_board) + 1):\n",
    "                for j in range(len(cur_hand)):\n",
    "                    if not cur_hand[j]:\n",
    "                        continue\n",
    "                    c = COLORS[j]\n",
    "                    # 第 1 个剪枝条件: 只在连续相同颜色的球的开头位置插入新球(在它前面插入过了，不需要再插入，意义相同)\n",
    "                    if i > 0 and cur_board[i - 1] == c:\n",
    "                        continue\n",
    "\n",
    "                    # 第 2 个剪枝条件: 只在以下两种情况放置新球\n",
    "                    #  - 第 1 种情况 : 当前后颜色相同且与当前颜色不同时候放置球\n",
    "                    #  - 第 2 种情况 : 当前球颜色与后面的球的颜色相同\n",
    "                    choose = False\n",
    "                    if 0 < i < len(cur_board) and cur_board[i - 1] == cur_board[i] and cur_board[i - 1] != c:\n",
    "                        choose = True\n",
    "                    if i < len(cur_board) and cur_board[i] == c:\n",
    "                        choose = True\n",
    "\n",
    "                    if choose:\n",
    "                        cp = list(cur_hand)\n",
    "                        cp[j] -= 1\n",
    "                        b2, h2 = clean(cur_board[:i] + c + cur_board[i:]), tuple(cp)\n",
    "                        if not b2:\n",
    "                            return step + 1\n",
    "                        if (b2, h2) not in visited:\n",
    "                            queue.append((b2, h2, step + 1))\n",
    "                            visited.add((b2, h2))\n",
    "                            visited.add((b2[::-1], h2))\n",
    "\n",
    "        return -1\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinStep(self, board: str, hand: str) -> int:\n",
    "        def remove(b):\n",
    "            n = 1\n",
    "            while n:\n",
    "                b, n = re.subn(r'(.)\\1{2,}', '', b)\n",
    "            return b\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dfs(b, h):\n",
    "            b = remove(b)\n",
    "            if b and not h: return float('inf')\n",
    "            if not b: return 0\n",
    "            res = float('inf')\n",
    "            for i in range(len(b)):\n",
    "                for j in range(len(h)):\n",
    "                    if j > 0 and h[j] == h[j-1]: continue\n",
    "                    if i > 0 and b[i-1] == h[j]: continue\n",
    "                    choose = False\n",
    "                    if 0 < i and b[i-1] == b[i] and b[i] != h[j]: choose = True\n",
    "                    if b[i] == h[j]: choose = True\n",
    "                    if choose:\n",
    "                        res = min(res, 1+dfs(b[:i]+h[j]+b[i:], h[:j]+h[j+1:]))\n",
    "            return res\n",
    "        \n",
    "        hand = ''.join(sorted(hand))\n",
    "        res = dfs(board, hand)\n",
    "        return res if res != float('inf') else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinStep(self, board: str, hand: str) -> int:\n",
    "        def remove(b):\n",
    "            n = 1\n",
    "            while n:\n",
    "                b, n = re.subn(r'(.)\\1{2,}', '', b)\n",
    "            return b\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dfs(b, h):\n",
    "            b = remove(b)\n",
    "            if b and not h: return float('inf')\n",
    "            if not b: return 0\n",
    "            res = float('inf')\n",
    "            for i in range(len(b)):\n",
    "                for j in range(len(h)):\n",
    "                    if j > 0 and h[j] == h[j-1]: continue\n",
    "                    if i > 0 and b[i-1] == h[j]: continue\n",
    "                    choose = False\n",
    "                    if 0 < i and b[i-1] == b[i] and b[i] != h[j]: choose = True\n",
    "                    if b[i] == h[j]: choose = True\n",
    "                    if choose:\n",
    "                        res = min(res, 1+dfs(b[:i]+h[j]+b[i:], h[:j]+h[j+1:]))\n",
    "            return res\n",
    "        \n",
    "        hand = ''.join(sorted(hand))\n",
    "        res = dfs(board, hand)\n",
    "        return res if res != float('inf') else -1"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
